Editing Selection algorithm (section)

== Exact numbers of comparisons ==
[[File:Median of 5.svg|thumb|upright=0.9|Finding the median of five values using six comparisons. Each step shows the comparisons to be performed next as yellow line segments, and a [[Hasse diagram]] of the order relations found so far (with smaller=lower and larger=higher) as blue line segments. The red elements have already been found to be greater than  three others and so cannot be the median. The larger of the two elements in the final comparison is the median.]]
[[Donald Knuth|Knuth]] supplies the following triangle of numbers summarizing pairs of <math>n</math> and <math>k</math> for which the exact number of comparisons needed by an optimal selection algorithm is known. The {{nowrap|<math>n</math>th}} row of the triangle (starting with <math>n=1</math> in the top row) gives the numbers of comparisons for inputs of <math>n</math> values, and the {{nowrap|<math>k</math>th}} number within each row gives the number of comparisons needed to select the {{nowrap|<math>k</math>th}} smallest value from an input of that size. The rows are symmetric because selecting the {{nowrap|<math>k</math>th}} smallest requires exactly the same number of comparisons, in the worst case, as selecting the {{nowrap|<math>k</math>th}} {{nowrap|largest.{{r|knuth}}}}

{{center|0}}
{{center|1 &nbsp;&nbsp; 1}}
{{center|2 &nbsp;&nbsp; 3 &nbsp;&nbsp; 2}}
{{center|3 &nbsp;&nbsp; 4 &nbsp;&nbsp; 4 &nbsp;&nbsp; 3}}
{{center|4 &nbsp;&nbsp; 6 &nbsp;&nbsp; 6 &nbsp;&nbsp; 6 &nbsp;&nbsp; 4}}
{{center|5 &nbsp;&nbsp; 7 &nbsp;&nbsp; 8 &nbsp;&nbsp; 8 &nbsp;&nbsp; 7 &nbsp;&nbsp; 5}}
{{center|6 &nbsp;&nbsp; 8 &nbsp; 10 &nbsp; 10 &nbsp; 10 &nbsp; 8 &nbsp;&nbsp; 6}}
{{center|7 &nbsp;&nbsp; 9 &nbsp; 11 &nbsp; 12 &nbsp; 12 &nbsp; 11 &nbsp; 9 &nbsp;&nbsp; 7}}
{{center|8 &nbsp; 11 &nbsp; 12 &nbsp; 14 &nbsp; 14 &nbsp; 14 &nbsp; 12 &nbsp; 11 &nbsp; 8}}
{{center|9 &nbsp; 12 &nbsp; 14 &nbsp; 15 &nbsp; 16 &nbsp; 16 &nbsp; 15 &nbsp; 14 &nbsp; 12 &nbsp; 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> This describes 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}}