Floyd–Rivest algorithm
# Floyd–Rivest algorithm

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. It has an expected running time of O(n) and an expected number of comparisons of n + min(k, n − k) + $O(n^{1/2}$ $log^{1/2}$ n).

The algorithm was originally presented in a Stanford University technical report containing two papers, where it was referred to as SELECT and paired with PICK, or median of medians. It was subsequently published in Communications of the ACM, Volume 18: Issue 3.

## Algorithm

The Floyd-Rivest algorithm is a divide and conquer algorithm, sharing many similarities with quickselect. It uses sampling to help partition the list into three sets. It then recursively selects the kth smallest element from the appropriate set.

The general steps are:

* Select a small random sample S from the list L.
* From S, recursively select two elements, u and v, such that u < v. These two elements will be the pivots for the partition and are expected to contain the kth smallest element of the entire list between them (in a sorted list).
* Using u and v, partition S into three sets: A, B, and C. A will contain the elements with values less than u, B will contain the elements with values between u and v, and C will contain the elements with values greater than v.
* Partition the remaining elements in L (that is, the elements in L - S) by comparing them to u or v and placing them into the appropriate set. If k is smaller than half the number of the elements in L rounded up, then the remaining elements should be compared to v first and then only to u if they are smaller than v. Otherwise, the remaining elements should be compared to u first and only to v if they are greater than u.
* Based on the value of k, apply the algorithm recursively to the appropriate set to select the kth smallest element in L.

By using |S| = $Θ(n^{2/3}$ $log^{1/3}$ n), we can get n + min(k, n − k) + $O(n^{2/3}$ $log^{1/3}$ n) expected comparisons. We can get n + min(k, n − k) + $O(n^{1/2}$ $log^{1/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(n^{1/2}$ $log^{1/2}$ n) at Θ(n) processed elements) without unacceptable risk of the desired element being outside of B.

### Pseudocode version

The following pseudocode rearranges the elements between left and right, such that for some value k, where left ≤ k ≤ right, the kth element in the list will contain the (k − left + 1)th smallest value, with the ith element being less than or equal to the kth for all left ≤ i ≤ k and the jth element being larger or equal to for k ≤ j ≤ right:

