Time Bounds for Selection and Expected Time Bounds for Selection.

摘要

Two papers are given. In the first paper,the number of comparisons required to select the i-th smallest of n numbers is shown to be at most a linear function of n by analysis of a new selection algorithm --PICK. Specifically,no more than 5.4305 n comparisons are ever required. This bound is improved for extreme values of i,and a new lower bound on the requisite number of comparisons is also proved. In the second paper, a new selection algorithm is presented which is shown to be very efficient on the average,both theoretically and practically. The number of comparisons used to select the i-th smallest of n numbers is n +min(i,n-i): + o(n). A lower bound within 9% of the above formula is also derived. (Author)