Analysis of quickselect : an algorithm for order statistics
Mahmoud, Hosam M. ; Modarres, Reza ; Smythe, Robert T.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995), p. 255-276 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1995-01-01
@article{ITA_1995__29_4_255_0,
     author = {Mahmoud, Hosam M. and Modarres, Reza and Smythe, Robert T.},
     title = {Analysis of quickselect : an algorithm for order statistics},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {29},
     year = {1995},
     pages = {255-276},
     mrnumber = {1359052},
     zbl = {0838.68029},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1995__29_4_255_0}
}

Mahmoud, Hosam M.; Modarres, Reza; Smythe, Robert T. Analysis of quickselect : an algorithm for order statistics. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995) pp. 255-276. http://gdmltest.u-ga.fr/item/ITA_1995__29_4_255_0/

1. G. Brassard and P. Bratley, Algorithms: Theory and Practice, Prentice-Hall, Englewoord Cliffs, New Jersey, 1988. | MR 1013783 | Zbl 0643.68003

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

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. | MR 57518 | Zbl 0048.11804

4. Y. Chow and H. Teicher, Probability Theory, Springer Verlag, New York, 1978. | MR 513230 | Zbl 0399.60001

5. K. Chung, A Course in Probability Theory, Second Edition, Academic Press, Orlando, Florida, 1974. | MR 346858

6. L. Devroye, Exponential bounds for the running time of a selection algorithm, Journal of Computer and System Sciences, 1984, 29, pp. 1-7. | MR 761047 | Zbl 0555.68018

7. G. Gonnet and R. Baeza-Yates, Handbook of Algorithms and Data Structures in Pascal and C, Second Edition, Addison-Wesley, Reading, Massachusetts, 1991. | Zbl 0719.68001

8. P. Hennequin, Combinatorial Analysis of Quicksort Algorithm, RAIRO, Theoretical Informatics and Applications, 1989, 23, pp. 317-333. | Numdam | MR 1020477 | Zbl 0685.68058

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. | MR 142216 | Zbl 0108.13601

11. D. Knuth, The Art of Computer Programming, 3: Sorting and Searching, Addison-Wesley, Reading, Massachussetts, 1973. | MR 378456

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. | MR 395032 | Zbl 0354.62038

14. H. Mahmoud, Evolution of Rondom Search Trees, John Wiley, New York, 1992. | Zbl 0762.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. | MR 1166615 | Zbl 0825.68491

16. M. Régnier, A limiting distribution for Quicksort, RAIRO, Theoretical Informatics and Applications, 1989, 23, pp. 335-343. | Numdam | MR 1020478 | Zbl 0677.68072

17. U. Rösler, A limit theorem for "QUICKSORT", RAIRO, Theoretical Informatics and Applications, 1991, 25, pp. 85-100. | Numdam | MR 1104413 | Zbl 0718.68026

18. R. Sedgewick, Quicksort with equal keys, SIAM J. on Computing, 1977, 6, pp. 240-267. | MR 449004 | Zbl 0356.68053

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

20. R. Sedgewick, Quicksort, Garland, New York, 1980.

21. R. Sedgewick, Algorithms, Second edition, Addison-Wesley, Reading, Massachusetts, 1988. | Zbl 0529.68002