In computer science, the Floyd-Rivest algorithm is a selection algorithm developed by Robert W. Floyd and Ronald L. Rivest that has an optimal expected number of comparisons within lower-order terms.
It is functionally equivalent to quickselect, but runs faster in practice on average.
[2] It was subsequently published in Communications of the ACM, Volume 18: Issue 3.
The general steps are: By using |S| = Θ(n2/3 log1/3 n), we can get n + min(k, n − k) + O(n2/3 log1/3 n) expected comparisons.
We can get n + min(k, n − k) + O(n1/2 log1/2 n) expected comparisons by starting with a small S and repeatedly updating u and v to keep the size of B small enough (O(n1/2 log1/2 n) at Θ(n) processed elements) without unacceptable risk of the desired element being outside of B.