Home → Magazine Archive → March 1975 (Vol. 18, No. 3) → Expected time bounds for selection → Abstract

Expected time bounds for selection

By Robert W. Floyd, Ronald L. Rivest

Communications of the ACM, Vol. 18 No. 3, Pages 165-172

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 ith smallest of n numbers is n + min(i,n-i) + o(n). A lower bound within 9 percent of the above formula is also derived.

The full text of this article is premium content


No entries found