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.
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.