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

Rudolf Grübel

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1999)

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

How to cite

top

Grübel, Rudolf. "On the median-of-$k$ version of Hoare’s selection algorithm." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 33.2 (1999): 177-192. <http://eudml.org/doc/92598>.

@article{Grübel1999,
author = {Grübel, Rudolf},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {selection algorithm},
language = {eng},
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/92598},
volume = {33},
year = {1999},
}

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
PB - EDP-Sciences
VL - 33
IS - 2
SP - 177
EP - 192
LA - eng
KW - selection algorithm
UR - http://eudml.org/doc/92598
ER -

References

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