
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 fixedpoint equation. We give an algorithm for perfect
random variate
generation from this distribution.

Full text: PDF  PostScript
Pages: 9599
Published on: June 5, 2000

Bibliography

Cramer, M. (1996),
A note concerning the limit distribution of the quicksort algorithm,
RAIRO Inform.
Théor. Appl.
30, 195207.
Math. Review 97e:68018

Devroye, L. (1986),
Nonuniform Random Variate Generation.
SpringerVerlag, New York.
Math. Review
87i:65012

Devroye, L. (1999),
Simulating perpetuities.
Preprint available from
http://cgm.cs.mcgill.ca/~luc/rng.ht
ml.
Math. Review number not available.

Fill, J. A. (1996),
On the distribution for binary search trees under the random permutation
model,
Random
Structures Algorithms
8, 125.
Math. Review 97f:68021

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 VersaillesSt. Quentin,
Versailles, France,
September, 2000).
Preprint available from
http://www.mts.jhu.edu/~fill/.
Math. Review number not available.

Fill, J. A.
and Janson, S. (2000),
Quicksort asymptotics.
Unpublished manuscript. Math. Review number not available.

Hennequin, P. (1989),
Combinatorial analysis of quicksort algorithm,
RAIRO Inform.
Théor. Appl.
23, 317333.
Math. Review 90k:68131

Régnier, M
. (1989),
A limiting distribution for quicksort,
RAIRO Inform.
Théor. Appl.
23, 335343.
Math. Review 90k:68132

Rösler,
U. (1991),
A limit theorem for `Quicksort',
RAIRO Inform.
Théor. Appl.
25, 85100.
Math. Review 92f:68028

Tan, K. H., and
Hadjicostas,
P. (1995),
Some properties of a limiting distribution in Quicksort,
Statist.
Probab. Lett.,
25, 8794.
Math. Review 96j:68049


