Revision as of 00:48, 30 January 2013 edit 132.217.254.1 (talk) →Important notes: Wording ← Previous edit		Revision as of 04:45, 31 January 2013 edit undo 171.66.165.89 (talk) →Partition-based general selection algorithm: It's meaningless to say "quickselect is 10 times faster than quicksort"; that depends on n. Remove unsourced claim that it is hard to implement. Next edit →
Line 76: 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''<sup>2</sup>) 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 very easy pseudo code, unlike the quicksort, the quickselect algorithm is notoriously hard to get right, mainly because of the many different edge cases like repeating values. However, if done properly, a Java implementation is typically a magnitude (10x) faster than the quicksort algorithm. <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 ==

Selection algorithm: Difference between revisions