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: Download PDF | View PDF online (requires PDF plugin)

Pages: 95-99

Publication Date: June 5, 2000

DOI: 10.1214/ECP.v5-1024

References

  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
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.