zbMATH — the first resource for mathematics

A limit theorem for “Quicksort”. (English) Zbl 0718.68026
Summary: Let \(X_ n\) be the number of comparisons needed by the sorting algorithm Quicksort to sort a list of n numbers into their natural ordering. We show that \((X_ n-E(X_ n))/n\) converges weakly to some random variable Y. The distribution of Y is characterized as the fixed point of some contraction. It satisfies a recursive equation, which is used to provide recursive relations for the moments. The random variable Y has exponential tails. Therefore the probability that Quicksort performs badly, e.g. that \(X_ n\) is larger than 2 E(X\({}_ n)\) converges polynomially fast of every order to zero.

68P10 Searching and sorting
Full Text: DOI EuDML
[1] 1. S. CAMBANIS, G. SIMON and W. STOUT, Inequalities for Ek (X, Y) when the Marginals are Fixed, Zeitschrift für Wahrscheinlichkeistheorie und verwandte Gebiete, 1976, 36, pp. 285-294. Zbl0325.60002 MR420778 · Zbl 0325.60002 · doi:10.1007/BF00532695
[2] 2. M. DENKER and U. RÖSLER, A Moment Estimate for Rank Statistics, Journal of Statistical Planning and Interference, 1985, 12, pp. 269-284. Zbl0591.62033 MR818380 · Zbl 0591.62033 · doi:10.1016/0378-3758(85)90076-X
[3] 3. L. DEVROYE, Exponential Bounds for the Running Time of a Selection Algorithm, Journal of Computer and System Sciences, 1985, 29, pp. 1-7. Zbl0555.68018 MR761047 · Zbl 0555.68018 · doi:10.1016/0022-0000(84)90009-6
[4] 4. N. DUNFORD and J. SCHWARTZ, Linear Operators I, John Wiley & Sorts, 1963. · Zbl 0128.34803
[5] 5. W. D. FRAZER and A. C. MCKELLAR, Samplesort: A Sampling Approach to Minimal Storage Tree Sorting, Journal of the Association for Computing Machinery, 1970, 17, pp. 496-507. Zbl0205.19202 MR287744 · Zbl 0205.19202 · doi:10.1145/321592.321600
[6] 6. P. HENNEQUIN, Combinatorial Analysis of Quicksort Algorithm, Informatique théorique et Applications/Theoretical Informatics and Applications, 1989, 23, pp. 317-333. Zbl0685.68058 MR1020477 · Zbl 0685.68058 · eudml:92337
[7] 7. C. A. R. HOARE, Algorithm 64: Quicksort, Communications of the Association for Computing Machinery, 1961, 4, p. 321.
[8] 8. C. A. R. HOARE, Quicksort, Computer Journal, 1962, 5, pp. 10-15. Zbl0108.13601 MR142216 · Zbl 0108.13601 · doi:10.1093/comjnl/5.1.10
[9] 9. D. E. KNUTH, The art of computer programming, 3, Sorting and searching, M. A. Reading, Addison-Wesley, 1973. MR378456 · Zbl 0302.68010
[10] 10. R. LOESER, Some Performance Tests of ”Quicksort” and Descendants, Communications of the Association for Computing Machinery 1974, 17, pp. 143-152.
[11] 11. P. MAJOR, On the invariance principle for sums of independent identically distributed random variables, Journal of Multivariate Analysis, 1978, 8, pp. 487-517. Zbl0408.60028 MR520959 · Zbl 0408.60028 · doi:10.1016/0047-259X(78)90029-5
[12] 12. M. RÉGNIER, A Limit Distribution for Quicksort, Informatique théorique et Applications/Theoretical Informatics and Applications, 1989, 23, pp. 335-343. Zbl0677.68072 MR1020478 · Zbl 0677.68072 · eudml:92338
[13] 13. R. SEDGEWICK, The analysis of Quicksort programs, Acta Informatica, 1977, 7, pp. 327-355. Zbl0325.68016 MR451845 · Zbl 0325.68016 · doi:10.1007/BF00289467
[14] 14. R. SEDGEWICK, Quicksort, Stanford Computer Science Report STAN-CS-75-492, Ph. d. thesis, 1975, Also published by Garland, Pub. Co., New York, 1980.
[15] 15. R. SEDGEWICK, Algorithms, Addison-Wesley, second edition, 1988. Zbl0717.68005 · Zbl 0717.68005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.