Content deleted Content added
more on where the numbers of comparisons come from |
|||
Line 66:
{{center|8 11 12 14 14 14 12 11 8}}
{{center|9 12 14 15 16 16 15 14 12 9}}
Most, but not all, of the entries on the left half of each row can be found using the formula <math display=block>n-k+(k-1)\bigl\lceil\log_2(n+2-k)\bigr\rceil</math> describing the number of comparisons made by a method of Abdollah Hadian and [[Milton Sobel]], related to heapselect, that finds the smallest value using a single-elimination tournament and then repeatedly uses a smaller tournament among the values eliminated by the eventual tournament winners to find the next successive values until reaching the {{nowrap|<math>k</math>th}} smallest.{{r|knuth|hadsob}} Some of the larger entries were proven to be optimal using a computer search.{{r|knuth|gkp}}
== Language support ==
Line 244 ⟶ 246:
| volume = 13
| year = 1984}}</ref>
<ref name=gkp>{{cite journal
| last1 = Gasarch | first1 = William | author1-link = William Gasarch
| last2 = Kelly | first2 = Wayne
| last3 = Pugh | first3 = William
| date = July 1996
| doi = 10.1145/235767.235772
| issue = 2
| journal = [[ACM SIGACT News]]
| pages = 88–96
| title = Finding the {{nowrap|<math>i</math>th}} largest of <math>n</math> for small <math>i,n</math>
| volume = 27}}</ref>
<ref name=gootam>{{cite book|title=Algorithm Design and Applications|first1=Michael T.|last1=Goodrich|author1-link= Michael T. Goodrich|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|publisher=Wiley|year=2015|chapter=9.2: Selection|pages=270–275|isbn=978-1-118-33591-8}}</ref>
Line 256 ⟶ 270:
| volume = 35
| year = 1992}}</ref>
<ref name=hadsob>{{cite report|first1=Abdollah|last1=Hadian|first2=Milton|last2=Sobel|author2-link=Milton Sobel|hdl=11299/199105|series=School of Statistics Technical Reports|volume=121|publisher=University of Minnesota|title=Selecting the <math>t</math>th largest using binary errorless comparisons}}</ref>
<ref name=hoare>{{cite journal
| |||