Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Floyd–Rivest algorithm
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, the Floyd-Rivest algorithm is a <a href="/facts/Selection_algorithm/zyxLnxNf">selection algorithm</a> developed by <a href="/facts/Robert_W._Floyd/sTFRb3TH">Robert W. Floyd</a> and <a href="/facts/Ronald_L._Rivest/nQsIcAKa">Ronald L. Rivest</a> that has an optimal expected number of comparisons within <a href="/facts/Lower-order_terms/ao2wfY2p">lower-order terms</a>. It is functionally equivalent to <a href="/facts/Quickselect/KJmN0f4B">quickselect</a>, but runs faster in practice on average. It has an expected running time of <i>O</i>(<i>n</i>) and an expected number of comparisons of <i>n</i> + min(<i>k</i>, <i>n</i> − <i>k</i>) + <i>O</i>(<i>n</i>1/2 log1/2 <i>n</i>). </p><p>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 <a href="/facts/Median_of_medians/BXUWjeYr">median of medians</a>. It was subsequently published in <a href="/facts/Communications_of_the_ACM/Ix1DvEAk">Communications of the ACM</a>, Volume 18: Issue 3. </p>