Selection algorithm: Difference between revisions

Revision as of 14:09, 24 August 2013

Revision as of 14:59, 24 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. AnIn examplefact, ofan suchexact amedian linear-timeis median-selectionnot algorithmnecessary is– thean pivotapproximate strategymedian inis sufficient. In the [[median of medians]] selection algorithm, whilethe "medianpivot ofstrategy medians"computes itselfan isapproximate themedian resultingand quickselectuses algorithm,this usingas thepivot, medianrecursing ason a smaller set to compute this pivot. In practice the overhead of medianpivot selectioncomputation is significant, so these algorithms are generally not used, but it is of theoretical interest in relating these problems and 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).

Similarly, given a median-selection algorithm or general selection algorithm applied to find the median, one can use it as a pivot strategy in quicksort, obtaining a sorting algorithm. If the selection algorithm is optimal, meaning O(''n''), then the resulting sorting algorithm is optimal, meaning O(''n'' log ''n''). The median is the best pivot for sorting, as it evenly divides the data, and thus guarantees optimal sorting, assuming the selection algorithm is optimal. A sorting analog to median of medians exists, using the pivot strategy (approximate median) in quicksort, and similarly yields an optimal quicksort.

== Incremental sorting by selection ==