Analysis of quickselect : an algorithm for order statistics
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995) no. 4, pp. 255-276.
@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},
     pages = {255--276},
     publisher = {EDP-Sciences},
     volume = {29},
     number = {4},
     year = {1995},
     zbl = {0838.68029},
     mrnumber = {1359052},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1995__29_4_255_0/}
}
TY  - JOUR
AU  - Mahmoud, Hosam M.
AU  - Modarres, Reza
AU  - Smythe, Robert T.
TI  - Analysis of quickselect : an algorithm for order statistics
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1995
DA  - 1995///
SP  - 255
EP  - 276
VL  - 29
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1995__29_4_255_0/
UR  - https://zbmath.org/?q=an%3A0838.68029
UR  - https://www.ams.org/mathscinet-getitem?mr=1359052
LA  - en
ID  - ITA_1995__29_4_255_0
ER  - 
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) no. 4, pp. 255-276. http://www.numdam.org/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