Analysis of quickselect : an algorithm for order statistics
Hosam M. Mahmoud; Reza Modarres; Robert T. Smythe
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1995)
- Volume: 29, Issue: 4, page 255-276
- ISSN: 0988-3754
Access Full Article
topHow to cite
topReferences
top- 1. G. BRASSARD and P. BRATLEY, Algorithms: Theory and Practice, Prentice-Hall, Englewoord Cliffs, New Jersey, 1988. Zbl0643.68003MR1013783
- 2. S. CAMBANIS, G. SIMONS and W. STOUT, Inequalities for the expected value of K (x, y) when the marginals are fîxed, Zeit Wahrsch. Verw. Geb., 1976, 36, pp. 285-294. Zbl0325.60002MR420778
- 3. H. CHERNOFF, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Annals of Mathematical Statistics, 1952, 23, pp. 493-507. Zbl0048.11804MR57518
- 4. Y. CHOW and H. TEICHER, Probability Theory, Springer Verlag, New York, 1978. Zbl0399.60001MR513230
- 5. K. CHUNG, A Course in Probability Theory, Second Edition, Academic Press, Orlando, Florida, 1974. MR346858
- 6. L. DEVROYE, Exponential bounds for the running time of a selection algorithm, Journal of Computer and System Sciences, 1984, 29, pp. 1-7. Zbl0555.68018MR761047
- 7. G. GONNET and R. BAEZA-YATES, Handbook of Algorithms and Data Structures in Pascal and C, Second Edition, Addison-Wesley, Reading, Massachusetts, 1991. Zbl0719.68001
- 8. P. HENNEQUIN, Combinatorial Analysis of Quicksort Algorithm, RAIRO, Theoretical Informatics and Applications, 1989, 23, pp. 317-333. Zbl0685.68058MR1020477
- 9. C. HOARE, Find (Algorithm 65), Communications of the ACM, 1961, 4, pp. 321-322.
- 10. C. HOARE, Quicksort, The Computer Journal, 1962, 5, pp. 10-15. Zbl0108.13601MR142216
- 11. D. KNUTH, The Art of Computer Programming, 3: Sorting and Searching, Addison-Wesley, Reading, Massachussetts, 1973. Zbl0302.68010MR378456
- 12. R. KRUISE, Data Structures and Program Design, Second Edition, Prentice-Hall, Englewood Cliffs, New Jersey, 1987.
- 13. E. LEHMANN, Nonparametrics: Statistical Methods Based on Ranks, Holden-Day, San Francisco/McGraw-Hill, New York, 1975. Zbl0354.62038MR395032
- 14. H. MAHMOUD, Evolution of Rondom Search Trees, John Wiley, New York, 1992. Zbl0762.68033
- 15. H. MAHMOUD, A law of large numbers for path lengths in search trees, Chapter in Random Graphs: Vol. II, A. FRIEZE and TOMASZ LUCZAK, eds., John Wiley, New York, 1992. Zbl0825.68491MR1166615
- 16. M. RÉGNIER, A limiting distribution for Quicksort, RAIRO, Theoretical Informatics and Applications, 1989, 23, pp. 335-343. Zbl0677.68072MR1020478
- 17. U. RÖSLER, A limit theorem for "QUICKSORT", RAIRO, Theoretical Informatics and Applications, 1991, 25, pp. 85-100. Zbl0718.68026MR1104413
- 18. R. SEDGEWICK, Quicksort with equal keys, SIAM J. on Computing, 1977, 6, pp. 240-267. Zbl0356.68053MR449004
- 19. R. SEDGEWICK, The analysis of quicksort programs, Acta Informatica, 1977, 7, pp. 327-355. Zbl0325.68016MR451845
- 20. R. SEDGEWICK, Quicksort, Garland, New York, 1980.
- 21. R. SEDGEWICK, Algorithms, Second edition, Addison-Wesley, Reading, Massachusetts, 1988. Zbl0529.68002