Selection algorithm: Difference between revisions

Revision as of 15:49, 24 August 2013

Revision as of 04:35, 25 August 2013

Line 43:

=== Median selection as pivot strategy ===

{{see|Median of medians}}

A median-selection algorithm can be used to yield a general selection algorithm or sorting algorithm, by applying it as the pivot strategy in quickselect or quicksort; if the median-selection algorithm is asymptotically optimal (linear-time), the resulting selection or sorting algorithm is as well. In fact, an exact median is not necessary – an approximate median is sufficient. In the [[median of medians]] selection algorithm, the pivot strategy computes an approximate median and uses this as pivot, recursing on a smaller set to compute this pivot. In practice the overhead of pivot computation is significant, so these algorithms are generally not used, but itthis technique is of theoretical interest in relating these problemsselection and sorting algorithms.

In detail, given a median-selection algorithm, one can use it as a pivot strategy in quickselect, obtaining a selection algorithm. If the median-selection algorithm is optimal, meaning O(''n''), then the resulting general selection algorithm is also optimal, again meaning linear. This is because quickselect is a [[decrease and conquer]] algorithm, and using the median at each pivot means that at each step the search set decreases by half in size, so the overall complexity is a [[geometric series]] times the complexity of each step, and thus simply a constant times the complexity of a single step, in fact <math>2 = 1/(1-1/2)</math> times (summing the series).