A NOTE CONCERNING THE LIMIT DISTRIBUTION OF THE QUICKSORT ALGORITHM

摘要

We perform simulations in order to obtain information on the limit distribution of the Quicksort algorithm. This distribution is also correlated to the external path length of a binary search tree. It turns out that the lognormal distribution is a very good approximation for that distribution. However, by exact and numerical calculation of some moments we shall demonstrate that these distributions are not the same.%La distribution limite de Quicksort (qui est la même que la distribution limite de la longueur de cheminement externe dans les arbres binaires de recherche) est inconnue. Nous montrons ici, par simulation, que l'approximation de cette distribution par une loi log-normale est en pratique excellente. Cependant prouvons aussi, par le calcul précis de quelques moments, que la distribution limite de Quicksort n'est pas log-normale.