A Characterization of the Set of Fixed Points of the Quicksort Transformation

James Allen Fill (The Johns Hopkins University)
Svante Janson (Uppsala University)

Abstract


The limiting distribution $\mu$ of the normalized number of key comparisons required by the Quicksort sorting algorithm is known to be the unique fixed point of a certain distributional transformation $T$ - unique, that is, subject to the constraints of zero mean and finite variance. We show that a distribution is a fixed point of $T$ if and only if it is the convolution of $\mu$ with a Cauchy distribution of arbitrary center and scale. In particular, therefore, $\mu$ is the unique fixed point of $T$ having zero mean.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 77-84

Publication Date: May 26, 2000

DOI: 10.1214/ECP.v5-1021

References

  1. Chung, K. L. (1974), A Course in Probability Theory. Second edition. Academic Press, New York. Math. Review 49:11579
  2. Durrett, R. and Liggett, T. M. (1983), Fixed points of the smoothing transformation, Z. Wahrsch. Verw. Gebiete 64, 275-301. Math. Review 85e:60059
  3. 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 C olloquium 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.
  4. Guivarc'h, Y. (1990), Sur une extension de la notion de loi semi-stable, Ann. Inst. H. Poincaré Probab. Statist. 26, 261-285. Math. Review 91i:60141
  5. Knessl, C. and Szpankowski, W. (1999), Quicksort algorithm again revisited, Discrete Math. Theor. Comput. Sci. 3, 43-64. Math. Review 2000b:68052
  6. Liu, Q. (1998), Fixed points of a generalized smoothing transformation and applications to the branching random walk, Adv. in Appl. Probab. 30, 85-112. Math. Review 99f:60151
  7. Rösler, U. (1991), A limit theorem for `Quicksort', RAIRO Inform. Théor. Appl. 25, 85-100. Math. Review 92f:68028
  8. Rösler, U. (1992), A fixed point theorem for distributions, Stochastic Process. Appl. 42, 195-214. Math. Review 93k:60038
  9. Rösler, U. (1999), The analysis of stochastic divide and conquer algorithms, Algorithmica , to appear. Preprint available from http://www-computerlabor.math.uni-kiel.de/stochastik/roesler/e_research.html . Math. Review number not available.
  10. Rösler, U., and Rüschendorf, L. (1999), The contraction method for recursive algorithms, Algorithmica , to appear. Preprint available from http://www-computerlabor.math.uni-kiel.de/stochastik/roesler/e_research.html . Math. Review number not available.
Bookmark and Share


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