Floyd–Rivest algorithm

<h2 id="algorithm">Algorithm</h2>
The Floyd-Rivest algorithm is a <a href="/facts/Divide_and_conquer_algorithm/pC1X7Ws7">divide and conquer algorithm</a>, sharing many similarities with <a href="/facts/Quickselect/KJmN0f4B">quickselect</a>. It uses <a href="/facts/Sampling_(statistics)/kIb01xdL">sampling</a> to help partition the list into three sets. It then recursively selects the kth smallest element from the appropriate set.
The general steps are:

<ol><li>Select a small random sample S from the list L.</li>
<li>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).</li>
<li>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.</li>
<li>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.</li>
<li>Based on the value of k, apply the algorithm recursively to the appropriate set to select the kth smallest element in L.</li></ol>
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.

<h3>Pseudocode version</h3>
The following <a href="/facts/Pseudocode/XgN19duK">pseudocode</a> 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

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Quickselect/KJmN0f4B">Quickselect</a></li>
<li><a href="/facts/Introselect/cM7BADYe">Introselect</a></li>
<li><a href="/facts/Median_of_medians/BXUWjeYr">Median of medians</a></li></ul>

<ul><li><a href="/facts/Robert_W._Floyd/sTFRb3TH">Floyd, Robert W.</a>; <a href="/facts/Ron_Rivest/nQsIcAKa">Rivest, Ron L.</a> (March 1975). <a href="http://people.csail.mit.edu/rivest/pubs/FR75a.pdf">"Expected time bounds for selection"</a> (PDF). Communications of the ACM. 18 (3): 165–172. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F360680.360691">10.1145/360680.360691</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:3064709">3064709</a>.</li>
<li>Kiwiel, Krzysztof C. (30 November 2005). <a href="https://core.ac.uk/download/pdf/82672439.pdf">"On Floyd and Rivest's SELECT algorithm"</a> (PDF). Theoretical Computer Science. 347 (1–2): 214–238. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.tcs.2005.06.032">10.1016/j.tcs.2005.06.032</a>.</li>
<li>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. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.7.8672">10.1.1.7.8672</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1080%2F00207160512331331048">10.1080/00207160512331331048</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:16522119">16522119</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Floyd, Robert W.; Rivest, Ronald L. (1975). "Algorithm 489: The Algorithm SELECT—for Finding the ith Smallest of n elements" (PDF). Comm. ACM. 18 (3): 173. CiteSeerX 10.1.1.309.7108. doi:10.1145/360680.360694. S2CID 122069429. <a href="/wiki/Robert_W._Floyd" target="_blank">/wiki/Robert_W._Floyd</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">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. <a href="http://i.stanford.edu/pub/cstr/reports/cs/tr/73/349/CS-TR-73-349.pdf" target="_blank">http://i.stanford.edu/pub/cstr/reports/cs/tr/73/349/CS-TR-73-349.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
</ol>

Floyd–Rivest algorithm open-in-new

Floyd–Rivest algorithm