Expected time bounds for selection

Robert W. Floyd, Ronald L. Rivest · Communications of the ACM · 1975

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 percent of the above formula is also derived.

Cited by 279 works. doi:10.1145/360680.360691 Open-access PDF

Authors

References