Home | Contents | Submissions, editors, etc. | Login | Search | EJP
 Electronic Communications in Probability > Vol. 5 (2000) > Paper 12 open journal systems 


Perfect Simulation from the Quicksort Limit Distribution

Luc Devroye, McGill University
James Allen Fill, The Johns Hopkins University
Ralph Neininger, Universität Freiburg


Abstract
The weak limit of the normalized number of comparisons needed by the Quicksort algorithm to sort n randomly permuted items is known to be determined implicitly by a distributional fixed-point equation. We give an algorithm for perfect random variate generation from this distribution.


Full text: PDF

Pages: 95-99

Published on: June 5, 2000
Bibliography
  1. Cramer, M. (1996), A note concerning the limit distribution of the quicksort algorithm, RAIRO Inform. Théor. Appl. 30, 195-207. Math. Review 97e:68018
  2. Devroye, L. (1986), Nonuniform Random Variate Generation. Springer-Verlag, New York. Math. Review 87i:65012
  3. Devroye, L. (1999), Simulating perpetuities. Preprint available from http://cgm.cs.mcgill.ca/~luc/rng.ht ml. Math. Review number not available.
  4. Fill, J. A. (1996), On the distribution for binary search trees under the random permutation model, Random Structures Algorithms 8, 1-25. Math. Review 97f:68021
  5. Fill, J. A. and Janson, S. (2000), Smoothness and decay properties of the limiting Quicksort density function. To apppear in a book edited by D . Gardy and A. Mokkadem, published by Birkhäuser, and based on the Colloquium on Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities (University of Versailles-St. Quentin, Versailles, France, September, 2000). Preprint available from http://www.mts.jhu.edu/~fill/. Math. Review number not available.
  6. Fill, J. A. and Janson, S. (2000), Quicksort asymptotics. Unpublished manuscript. Math. Review number not available.
  7. Hennequin, P. (1989), Combinatorial analysis of quicksort algorithm, RAIRO Inform. Théor. Appl. 23, 317-333. Math. Review 90k:68131
  8. Régnier, M . (1989), A limiting distribution for quicksort, RAIRO Inform. Théor. Appl. 23, 335-343. Math. Review 90k:68132
  9. Rösler, U. (1991), A limit theorem for `Quicksort', RAIRO Inform. Théor. Appl. 25, 85-100. Math. Review 92f:68028
  10. Tan, K. H., and Hadjicostas, P. (1995), Some properties of a limiting distribution in Quicksort, Statist. Probab. Lett., 25, 87-94. Math. Review 96j:68049
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | EJP

Electronic Communications in Probability. ISSN: 1083-589X