Analysis of quickselect : an algorithm for order statistics
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 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  - 
%0 Journal Article
%A Mahmoud, Hosam M.
%A Modarres, Reza
%A Smythe, Robert T.
%T Analysis of quickselect : an algorithm for order statistics
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1995
%P 255-276
%V 29
%N 4
%I EDP-Sciences
%G en
%F 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, Volume 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 | Zbl

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 | Zbl

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 | Zbl

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

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

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 | Zbl

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

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

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 | Zbl

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

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 | Zbl

14. H. Mahmoud, Evolution of Rondom Search Trees, John Wiley, New York, 1992. | Zbl

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 | Zbl

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

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

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

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

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

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