Portal de Periódicos da CAPES

A note concerning the limit distribution of the quicksort algorithm

1996; EDP Sciences; Volume: 30; Issue: 3 Linguagem: Inglês

10.1051/ita/1996300301951

1290-385X

Michael Cramer,

Diffusion and Search Dynamics

We perform simulations in order to obtain information on the limit distribution of the Quicksort algorithm.This distribution is also correlated to the external pathlength 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.Résumé.-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 Vapproximation 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.