1-2hit |
Several basic properties of minimum-comparison selection algorithms are shown, and some exact values are obtained for Vt(n) for small n, where Vt(n) denotes the number of comparisons necessary to select the t-th largest of n elements. The upper bound for V5(10) is reduced to 16. Those results improve the table of the best upper bounds known for Vt(n) in the Knuth's book (Sorting and Searching).
Kohei NOSHITA Yoshinobu NAKATANI
This note shows a new implicit data structure, called a set of nested s-heaps, for deleting the maximum value of n elements in 2 long n comparisons. Nested s-heaps can be used to improve the efficiency of Smoothsort.