Selection algorithm: Difference between revisions

Revision as of 09:41, 10 April 2013

Revision as of 05:05, 11 April 2013

Line 77:

Like quicksort, the performance of the algorithm is sensitive to the pivot that is chosen. If bad pivots are consistently chosen, this degrades to the minimum-based selection described previously, and so can require as much as O(''n''²) time. David Musser describes a "median-of-3 killer" sequence that can force the well-known median-of-three pivot selection algorithm to fail with worst-case behavior (see ''[[#Introselect|Introselect]]'' section below).

Despite its easy pseudo code, unlike the quicksort, the quickselect algorithm is hard to get right - there aren't too many reliably working samples found online. It is mainly because of the many different edge cases like repeating values which can make the nth number hard to interpret and find. However, if done properly, a Java implementation is typically much faster than the quicksort algorithm, partly because it does not require recursion. <ref>{{cite web | first = Adam | last = Horvath | url = http://blog.teamleadnet.com/2012/07/quick-select-algorithm-find-kth-element.html | title = Quick select algorithm - find the Kth element in a list in linear time | date = July 23, 2012 }}</ref>

== Linear general selection algorithm - Median of Medians algorithm ==