A limit theorem for “quicksort”
Rösler, Uwe
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 25 (1991), p. 85-100 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_1991__25_1_85_0,
     author = {R\"osler, Uwe},
     title = {A limit theorem for ``quicksort''},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {25},
     year = {1991},
     pages = {85-100},
     mrnumber = {1104413},
     zbl = {0718.68026},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1991__25_1_85_0}
}

Rösler, Uwe. A limit theorem for “quicksort”. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 25 (1991) pp. 85-100. http://gdmltest.u-ga.fr/item/ITA_1991__25_1_85_0/

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. | MR 420778 | Zbl 0325.60002

2. M. Denker and U. Rösler, A Moment Estimate for Rank Statistics, Journal of Statistical Planning and Interference, 1985, 12, pp. 269-284. | MR 818380 | Zbl 0591.62033

3. L. Devroye, Exponential Bounds for the Running Time of a Selection Algorithm, Journal of Computer and System Sciences, 1985, 29, pp. 1-7. | MR 761047 | Zbl 0555.68018

4. N. Dunford and J. Schwartz, Linear Operators I, John Wiley & Sorts, 1963.

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. | MR 287744 | Zbl 0205.19202

6. P. Hennequin, Combinatorial Analysis of Quicksort Algorithm, Informatique théorique et Applications/Theoretical Informatics and Applications, 1989, 23, pp. 317-333. | Numdam | MR 1020477 | Zbl 0685.68058

7. C. A. R. Hoare, Algorithm 64: Quicksort, Communications of the Association for Computing Machinery, 1961, 4, p. 321.

8. C. A. R. Hoare, Quicksort, Computer Journal, 1962, 5, pp. 10-15. | MR 142216 | Zbl 0108.13601

9. D. E. Knuth, The art of computer programming, 3, Sorting and searching, M. A. Reading, Addison-Wesley, 1973. | MR 378456

10. R. Loeser, Some Performance Tests of "Quicksort" and Descendants, Communications of the Association for Computing Machinery 1974, 17, pp. 143-152.

11. P. Major, On the invariance principle for sums of independent identically distributed random variables, Journal of Multivariate Analysis, 1978, 8, pp. 487-517. | MR 520959 | Zbl 0408.60028

12. M. Régnier, A Limit Distribution for Quicksort, Informatique théorique et Applications/Theoretical Informatics and Applications, 1989, 23, pp. 335-343. | Numdam | MR 1020478 | Zbl 0677.68072

13. R. Sedgewick, The analysis of Quicksort programs, Acta Informatica, 1977, 7, pp. 327-355. | MR 451845 | Zbl 0325.68016

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. R. Sedgewick, Algorithms, Addison-Wesley, second edition, 1988. | Zbl 0717.68005