Expected time bounds for selection

Robert W. Floyd, Ronald L. Rivest

Communications of the ACM · 1975 · 280 citations · 4 references

DOIFull text

Open access

Concepts

Abstract

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.

References

4