A limit theorem for “quicksort”
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1991)
- Volume: 25, Issue: 1, page 85-100
- ISSN: 0988-3754
Access Full Article
topHow to cite
topRösler, Uwe. "A limit theorem for “quicksort”." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 25.1 (1991): 85-100. <http://eudml.org/doc/92383>.
@article{Rösler1991,
author = {Rösler, Uwe},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {Quicksort},
language = {eng},
number = {1},
pages = {85-100},
publisher = {EDP-Sciences},
title = {A limit theorem for “quicksort”},
url = {http://eudml.org/doc/92383},
volume = {25},
year = {1991},
}
TY - JOUR
AU - Rösler, Uwe
TI - A limit theorem for “quicksort”
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1991
PB - EDP-Sciences
VL - 25
IS - 1
SP - 85
EP - 100
LA - eng
KW - Quicksort
UR - http://eudml.org/doc/92383
ER -
References
top- 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.60002MR420778
- 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.62033MR818380
- 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.68018MR761047
- 4. N. DUNFORD and J. SCHWARTZ, Linear Operators I, John Wiley & Sorts, 1963. Zbl0128.34803
- 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.19202MR287744
- 6. P. HENNEQUIN, Combinatorial Analysis of Quicksort Algorithm, Informatique théorique et Applications/Theoretical Informatics and Applications, 1989, 23, pp. 317-333. Zbl0685.68058MR1020477
- 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. Zbl0108.13601MR142216
- 9. D. E. KNUTH, The art of computer programming, 3, Sorting and searching, M. A. Reading, Addison-Wesley, 1973. Zbl0302.68010MR378456
- 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. Zbl0408.60028MR520959
- 12. M. RÉGNIER, A Limit Distribution for Quicksort, Informatique théorique et Applications/Theoretical Informatics and Applications, 1989, 23, pp. 335-343. Zbl0677.68072MR1020478
- 13. R. SEDGEWICK, The analysis of Quicksort programs, Acta Informatica, 1977, 7, pp. 327-355. Zbl0325.68016MR451845
- 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. Zbl0717.68005
Citations in EuDML Documents
top- Rudolf Grübel, Anke Reimers, On the number of iterations required by Von Neumann addition
- Hosam M. Mahmoud, Reza Modarres, Robert T. Smythe, Analysis of quickselect : an algorithm for order statistics
- Michael Cramer, A note concerning the limit distribution of the quicksort algorithm
- Rudolf Grübel, Anke Reimers, On the number of iterations required by Von Neumann addition
NotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.