A NOTE CONCERNING THE LIMIT DISTRIBUTION OF THE QUICKSORT ALGORITHM

Authors
CRAMER M
Citation
M. Cramer, A NOTE CONCERNING THE LIMIT DISTRIBUTION OF THE QUICKSORT ALGORITHM, Informatique theorique et applications, 30(3), 1996, pp. 195-207
Citations number
8
Categorie Soggetti
Computer Sciences","Computer Science Information Systems
Journal title
Informatique theorique et applications → ACNP
ISSN journal
09883754
Volume
30
Issue
3
Year of publication
1996
Pages
195 - 207
Database
ISI
SICI code
0988-3754(1996)30:3<195:ANCTLD>2.0.ZU;2-3
Abstract
We perform simulations in order to obtain information on the limit dis tribution of the Quicksort algorithm. This distribution is also con el ated to the external path length of a binary search tree. II trims out that the lognormal distribution is a very good approximation Sor that distribution. However, by exact and numerical calculation of some mom ents lye shall demonstrate that these distributions are not the same.