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

Rudolf Grübel

RAIRO - Theoretical Informatics and Applications (2010)

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

Abstract

top
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.

How to cite

top

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

NotesEmbed ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.