Randomized selection with tripartitioning

Original · EN

We show that several versions of Floyd and Rivest's algorithm Select [Comm.ACM 18 (1975) 173] for finding the kth smallest of n elements require at most n+{k,n-k}+o(n) comparisons on average, even when equal elements occur. This parallels our recent analysis of another variant due to Floyd and Rivest [Comm. ACM 18 (1975) 165--172]. Our computational results suggest that both variants perform well in practice, and may compete with other selection methods, such as Hoare's Find or quickselect with median-of-3 pivots.