Floyd–Rivest algorithm
Class | Array |
---|---|
Average performance | n + min(k, n − k) + O(n1/2 log1/2 n) |
In
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.[2] It was subsequently published in Communications of the ACM, Volume 18: Issue 3.
Algorithm
The Floyd-Rivest algorithm is a
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| = Θ(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.
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
:
// 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) is while right > left do // 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 then 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 then swap array[right] and array[left] while i < j do swap array[i] and array[j] i := i + 1 j := j − 1 while array[i] < t do i := i + 1 while array[j] > t do j := j − 1 if array[left] = t then 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 then left := j + 1 if k ≤ j then right := j − 1
See also
References
- S2CID 122069429.
- ^ Two papers on the selection problem: Time Bounds for Selection and Expected Time Bounds for Selection (PDF) (Technical report). Stanford Computer Science Technical Reports and Technical Notes. April 1973. CS-TR-73-349.
- S2CID 3064709.
- Kiwiel, Krzysztof C. (30 November 2005). "On Floyd and Rivest's SELECT algorithm" (PDF). Theoretical Computer Science. 347 (1–2): 214–238. .
- 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. S2CID 16522119.