Floyd–Rivest algorithm

Floyd–Rivest

Class	Selection algorithm
Data structure	Array
Average performance	n + min(k, n − k) + O(n1/2)

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).

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 intelligently partition the list into smaller sets, narrowing towards the kth smallest element.

The fundamental steps are:

1. (initialize) Start with left and right being the first and last elements of the list. Pick the kth element of the list as pivot.
2. (partition) Squeeze in from left and right, by swapping the first element on the left that is greater than pivot with the first element on the right that is less than pivot. Continue this until left and right meet somewhere in the middle.
3. (shrink) After determining the final index of pivot, make the side containing the kth element the new list by updating left and right.
4. (repeat) Repeat the above steps until right is less than or equal to left.
5. (special case) Before all of these steps, if the list is very large (according to some pre-determined constant like 500) then first execute the above algorithm on a subset of the list surrounding the current kth element. This is the step that ensures O(n) runtime even for unfortunately selected pivots.

Pseudocode version

The following pseudocode sorts the elements between left and right in ascending order, 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:

 // left is the left index for the interval
 // right is the right index for the interval
 // k is the desired index value, where array[k] is the (k+1)th smallest element when left = 0
 function select(array, left, right, k)
     while right > left
         // use select recursively to sample a smaller set of size s
         // the arbitrary constants 600 and 0.5 are used in the original
         // version to minimize execution time
         if right - left > 600
             n := right - left + 1
             i := k - left + 1
             z := ln(n)
             s := 0.5 * exp(2 * z/3)
             sd := 0.5 * sqrt(z * s * (n - s)/n) * sign(i - n/2)
             newLeft = max(left, k - i * s/n + sd)
             newRight = min(right, k + (n - i) * s/n + sd)
             select(array, newLeft, newRight, k)
         // partition the elements between left and right around t
         t := array[k] 
         i := left
         j := right
         swap array[left] and array[k]
         if array[right] > t 
             swap array[right] and array[left]
         while i < j
             swap array[i] and array[j]
             i := i + 1
             j := j - 1
             while array[i] < t
                 i := i + 1
             while array[j] > t
                 j := j - 1
         if array[left] = t
             swap array[left] and array[j]
         else
             j := j + 1
             swap array[j] and array[right]
         // adjust left and right towards the boundaries of the subset
         // containing the (k - left + 1)th smallest element
         if j ≤ k
             left := j + 1
         if k ≤ j 
             right := j - 1

See also

• Quickselect
• Introselect
• Median of medians

References

• Floyd, Robert W.; Rivest, Ron L. (March 1975). "Expected time bounds for selection" (PDF). Communications of the ACM. 18 (3): 165–172. doi:10.1145/360680.360691.
• Kiwiel, Krzysztof C. (30 November 2005). "On Floyd and Rivest's SELECT algorithm" (PDF). Theoretical Computer Science. 347 (1–2): 214–238. doi:10.1016/j.tcs.2005.06.032.
• Gerbessiotis, Alexandros V.; Siniolakis, Constantinos J.; Paraskevi, Aghia (May 2005). "A probabilistic analysis of the Floyd-Rivest expected time selection algorithm". International Journal of Computer Mathematics. 82 (5): 509–519. CiteSeerX 10.1.1.7.8672.