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
topHow 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.
- P. Bickel and D.A. Freedman, Some asymptotic theory for the bootstrap. Annals of Statistics9 (1981) 1196-1217.
- 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.
- L. Devroye, Exponential bounds for the running time of a selection algorithm. J. Comput. System Sci.29 (1984) 1-7.
- N. Dunford and J.T. Schwartz, Linear Operators, Part I: General Theory. Wiley, New York (1958).
- R.W. Floyd and R.L. Rivest, Expected time bounds for selection. Comm. ACM18 (1975) 165-172.
- R. Grübel and U. Rösler, Asymptotic distribution theory for Hoare's selection algorithm. Adv. in Applied Probab.28 (1996) 252-269.
- R. Grübel, Hoare's selection algorithm: A Markov chain approach. J. Appl. Probab.35 (1998) 36-45.
- 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.
- D.E. Knuth, The Art of Computer Programming3, Sorting and Searching. Addison-Wesley, Reading (1973).
- B. Kodaj and T.F. Mori, On the number of comparisons in Hoare's algorithm ``Find''. Studia Sci. Math. Hungar.33 (1997) 185-207.
- J. Neveu, Mathematische Grundlagen der Wahrscheinlichkeitstheorie. Oldenbourg, München (1969).
- V. Paulsen, The moments of FIND. J. Appl. Probab.34 (1997) 1079-1082.
- G.J.E. Rawlins, Compared to What? An Introduction to the Analysis of Algorithms. Freedman, New York (1992).
- R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms. Addison-Wesley, Reading (1996).
Citations in EuDML Documents
topNotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.