# On the median-of-k version of Hoare's selection algorithm

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 33, Issue: 2, page 177-192
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topGrübel, Rudolf. "On the median-of-k version of Hoare's selection algorithm." RAIRO - Theoretical Informatics and Applications 33.2 (2010): 177-192. <http://eudml.org/doc/221976>.

@article{Grübel2010,

abstract = {
In Hoare's (1961) original version of the algorithm
the partitioning element in the central divide-and-conquer
step is chosen uniformly at random from the set S in question.
Here we consider a variant where this element is the median
of a sample of size 2k+1 from S. We investigate convergence
in distribution of the number of comparisons required and obtain
a simple explicit result for the limiting
average performance of the median-of-three version.
},

author = {Grübel, Rudolf},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Randomized algorithms; average performance;
asymptotic distribution.; selection algorithm},

language = {eng},

month = {3},

number = {2},

pages = {177-192},

publisher = {EDP Sciences},

title = {On the median-of-k version of Hoare's selection algorithm},

url = {http://eudml.org/doc/221976},

volume = {33},

year = {2010},

}

TY - JOUR

AU - Grübel, Rudolf

TI - On the median-of-k version of Hoare's selection algorithm

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 33

IS - 2

SP - 177

EP - 192

AB -
In Hoare's (1961) original version of the algorithm
the partitioning element in the central divide-and-conquer
step is chosen uniformly at random from the set S in question.
Here we consider a variant where this element is the median
of a sample of size 2k+1 from S. We investigate convergence
in distribution of the number of comparisons required and obtain
a simple explicit result for the limiting
average performance of the median-of-three version.

LA - eng

KW - Randomized algorithms; average performance;
asymptotic distribution.; selection algorithm

UR - http://eudml.org/doc/221976

ER -

## References

top- D.H. Anderson and R. Brown, Combinatorial aspects of C.A.R. Hoare's FIND algorithm. Australasian J. Combinatorics5 (1992) 109-119. Zbl0752.68021
- P. Bickel and D.A. Freedman, Some asymptotic theory for the bootstrap. Annals of Statistics9 (1981) 1196-1217. Zbl0449.62034
- 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. Zbl0278.68033
- L. Devroye, Exponential bounds for the running time of a selection algorithm. J. Comput. System Sci.29 (1984) 1-7. Zbl0555.68018
- N. Dunford and J.T. Schwartz, Linear Operators, Part I: General Theory. Wiley, New York (1958). Zbl0084.10402
- R.W. Floyd and R.L. Rivest, Expected time bounds for selection. Comm. ACM18 (1975) 165-172. Zbl0296.68049
- R. Grübel and U. Rösler, Asymptotic distribution theory for Hoare's selection algorithm. Adv. in Applied Probab.28 (1996) 252-269. Zbl0853.60033
- R. Grübel, Hoare's selection algorithm: A Markov chain approach. J. Appl. Probab.35 (1998) 36-45. Zbl0913.60059
- C.A.R. Hoare, Algorithm 63: PARTITION, Algorithm 64: QUICKSORT, Algorithm 65: FIND. Comm. ACM4 (1961) 321-322.
- L. Hyafil, Bounds for selection. SIAM J. Comput.5 (1976) 109-114. Zbl0324.68028
- D.E. Knuth, The Art of Computer Programming3, Sorting and Searching. Addison-Wesley, Reading (1973). Zbl0302.68010
- B. Kodaj and T.F. Mori, On the number of comparisons in Hoare's algorithm ``Find''. Studia Sci. Math. Hungar.33 (1997) 185-207. Zbl0910.60002
- J. Neveu, Mathematische Grundlagen der Wahrscheinlichkeitstheorie. Oldenbourg, München (1969). Zbl0174.21201
- V. Paulsen, The moments of FIND. J. Appl. Probab.34 (1997) 1079-1082. Zbl0892.60100
- G.J.E. Rawlins, Compared to What? An Introduction to the Analysis of Algorithms. Freedman, New York (1992). Zbl0824.68044
- R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms. Addison-Wesley, Reading (1996). Zbl0841.68059