Institution: Stanford University, Department of Computer Science

Title: Two papers on the selection problem: Time Bounds for Selection [by Manual Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan] and Expected Time Bounds for Selection [by Robert W. Floyd and Ronald L. Rivest].

Author: Blum, Manual

Author: Floyd, Robert W.

Author: Pratt, Vaughan R.

Author: Rivest, Ronald L.

Author: Tarjan, Robert Endre

Date: April 1973

Abstract: (1) 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. (2) 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.

http://i.stanford.edu/pub/cstr/reports/cs/tr/73/349/CS-TR-73-349.pdf