On the median-of-k version of Hoare’s selection algorithm
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) no. 2, pp. 177-192.
@article{ITA_1999__33_2_177_0,
     author = {Gr\"ubel, Rudolf},
     title = {On the median-of-$k$ version of {Hoare{\textquoteright}s} selection algorithm},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {177--192},
     publisher = {EDP-Sciences},
     volume = {33},
     number = {2},
     year = {1999},
     mrnumber = {1707969},
     zbl = {0946.68058},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_1999__33_2_177_0/}
}
TY  - JOUR
AU  - Grübel, Rudolf
TI  - On the median-of-$k$ version of Hoare’s selection algorithm
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1999
SP  - 177
EP  - 192
VL  - 33
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1999__33_2_177_0/
LA  - en
ID  - ITA_1999__33_2_177_0
ER  - 
%0 Journal Article
%A Grübel, Rudolf
%T On the median-of-$k$ version of Hoare’s selection algorithm
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1999
%P 177-192
%V 33
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1999__33_2_177_0/
%G en
%F ITA_1999__33_2_177_0
Grübel, Rudolf. On the median-of-$k$ version of Hoare’s selection algorithm. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) no. 2, pp. 177-192. http://archive.numdam.org/item/ITA_1999__33_2_177_0/

[1] D. H. Anderson and R. Brown, Combinatorial aspects of C.A.R. Hoare's FIND algorithm. Australasian J. Combinatorics 5 (1992) 109-119. | MR | Zbl

[2] P. Bickel and D. A. Freedman, Some asymptotic theory for the bootstrap. Annals of Statistics 9 (1981) 1196-1217. | MR | Zbl

[3] M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest and R. E. Tarjan, Time bounds for selection. J. Comput. System Sci. 7 (1973) 448-461. | MR | Zbl

[4] L. Devroye, Exponential bounds for the running time of a selection algorithm. J. Comput. System Sci. 29 (1984) 1-7. | MR | Zbl

[5] N. Dunford and J. T. Schwartz, Linear Operators, Part I: General Theory. Wiley, New York (1958). | MR | Zbl

[6] R. W. Floyd and R. L. Rivest, Expected time bounds for selection. Comm. ACM 18 (1975) 165-172. | Zbl

[7] R. Grübel and U. Rösler, Asymptotic distribution theory for Hoare's selection algorithm. Adv. in Applied Probab. 28 (1996) 252-269. | MR | Zbl

[8] R. Grübel, Hoare's selection algorithm: A Markov chain approach. J. Appl. Probab. 35 (1998) 36-45. | MR | Zbl

[9] C. A. R. Hoare, Algorithm 63: PARTITION, Algorithm 64: QUICKSORT, Algorithm 65: FIND. Comm. ACM 4 (1961) 321-322.

[10] L. Hyafil, Bounds for selection. SIAM J. Comput. 5 (1976) 109-114. | MR | Zbl

[11] D. E. Knuth, The Art of Computer Programming 3, Sorting and Searching. Addison-Wesley, Reading (1973). | MR

[12] B. Kodaj and T. F. Mori, On the number of comparisons in Hoare's algorithm "Find". Studia Sci. Math. Hungar. 33 (1997) 185-207. | MR | Zbl

[13] J. Neveu, Mathematische Grundlagen der Wahrscheinlichkeitstheorie. Oldenbourg, München (1969). | MR | Zbl

[14] V. Paulsen, The moments of FIND. J. Appl. Probab. 34 (1997) 1079-1082. | MR | Zbl

[15] G. J. E. Rawlins, Compared to What ? An Introduction to the Analysis of Algorithms. Freedman, New York (1992). | Zbl

[16] R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms. Addison-Wesley, Reading (1996). | Zbl