Report Number: CS-TR-73-349
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