Content deleted Content added
blogs are inalid references for wikipedia Undid revision 549654413 by 121.44.73.25 (talk) |
Change text description of worst case performance to match every other worst case performance mentioned in the article. |
||
Line 92:
A worst-case linear algorithm for the general case of selecting the ''k''th largest element was published by [[Manuel Blum|Blum]], [[Robert Floyd|Floyd]], [[Vaughan Ronald Pratt|Pratt]], [[Ron Rivest|Rivest]] and [[Robert Tarjan|Tarjan]] in their 1973 paper "Time bounds for selection", sometimes called '''BFPRT''' after the last names of the authors. It is based on the quickselect algorithm and is also known as the '''median-of-medians algorithm'''.
Although quickselect is linear-time on average, it can require quadratic time with poor pivot choices (consider the case of pivoting around the largest element at each step). The solution to make it O(
The ''Select'' algorithm divides the list into groups of five elements. (Left over elements are ignored for now.) Then, for each group of five, the median is calculated (an operation that can potentially be made very fast if the five values can be loaded into [[Processor register|registers]] and compared). (If sorting in-place, then these medians are moved into one contiguous block in the list.) ''Select'' is then called recursively on this sublist of ''n''/5 elements to find their true median. Finally, the "median of medians" is chosen to be the pivot.
| |||