Floyd–Rivest algorithm
| Class | Selection algorithm |
|---|---|
| Data structure | Array |
| Average performance |
In computer science, the Floyd–Rivest algorithm is a highly efficient selection algorithm – its expected number of comparisons is optimal to within lower-order terms.
The algorithm was originally presented in a Stanford University technical report containing two papers, where it was paired with median of medians.[1]
It was subsequently published in Floyd & Rivest (1975).
In the original paper the algorithm is referred to as SELECT; contrast with FIND for quickselect and PICK for median of medians.
References
- ^ "Two papers on the selection problem: Time Bounds for Selection and Expected Time Bounds for Selection" CS-TR-73-349, Stanford Computer Science Technical Reports and Technical Notes, April 1973
- Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/360680.360691, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1145/360680.360691instead. - Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1016/j.tcs.2005.06.032, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1016/j.tcs.2005.06.032instead. - "A probabilistic analysis of the Floyd-Rivest expected time selection algorithm" (2002), by Alexandros V. Gerbessiotis , Constantinos J. Siniolakis , Aghia Paraskevi
 | This computer science article is a stub. You can help Wikipedia by expanding it. |