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(n1/2 log1/2 n).
- Class
- Selection algorithm
- Comment
- enIn 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(n1/2 log1/2 n).
- Data
- Array data structure
- Has abstract
- enIn 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(n1/2 log1/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.
- Hypernym
- Algorithm
- Is primary topic of
- Floyd–Rivest algorithm
- Label
- enFloyd–Rivest algorithm
- Link from a Wikipage to an external page
- core.ac.uk/download/pdf/82672439.pdf%7C
- people.csail.mit.edu/rivest/pubs/FR75a.pdf
- Link from a Wikipage to another Wikipage
- Array data structure
- Category:Selection algorithms
- Communications of the ACM
- Computer science
- Divide and conquer algorithm
- Introselect
- Lower-order terms
- Median of medians
- Pseudocode
- Quickselect
- Robert W. Floyd
- Ronald L. Rivest
- Sampling (statistics)
- Selection algorithm
- Name
- enFloyd–Rivest
- SameAs
- fDeo
- m.0wzx02y
- Q17047365
- Subject
- Category:Selection algorithms
- WasDerivedFrom
- Floyd–Rivest algorithm?oldid=1096413384&ns=0
- WikiPageLength
- 7707
- Wikipage page ID
- 40417327
- Wikipage revision ID
- 1096413384
- WikiPageUsesTemplate
- Template:Cite journal
- Template:Infobox Algorithm
- Template:Math
- Template:Refbegin
- Template:Refend
- Template:Reflist