Floyd–Rivest algorithm

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 and an expected number of comparisons of . The algorithm was originally presented in a 1973 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.

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 and an expected number of comparisons of . The algorithm was originally presented in a 1973 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 2/3 log 1/3 n), we can get expected comparisons. We can get 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 : // 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 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

Quickselect Introselect Median of medians

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1375097835 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001375097835 · captured 1789500592.0 · version history

Cite this page as: encyclopegia.org, “Floyd–Rivest algorithm”, snapshot enwiki-001375097835. https://encyclopegia.org/a/floyd-rivest-algorithm

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.