Revision as of 20:24, 2 April 2023 edit David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,585 edits m →Lower bounds: split long sentence ← Previous edit		Revision as of 20:27, 2 April 2023 edit undo David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,585 edits →Exact numbers of comparisons: another long sentence Next edit →
Line 70: {{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~~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}} == Language support ==

Selection algorithm: Difference between revisions