Content deleted Content added
→Partition-based selection: selection and sorting |
→Partition-based selection: elab medians |
||
Line 39:
* [[Quickselect]] ([[Quicksort]])
* [[Median of medians]]▼
* [[Introselect]] ([[Introsort]])
=== Median selection as pivot strategy ===
In fact, given a selection algorithm, one can use it as a pivot strategy in a 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''). Specifically, given a median selection algorithm – a general selection algorithm applied to find to median, or a specialized algorithm for the median – as pivot strategy one chooses the median of each interval as the pivot. 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. In practice the overhead of selecting is significant, so this is generally not used, but this is of theoretical interest in showing how a selection algorithm can yield a sorting algorithm.▼
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. An example of such a linear-time median-selection algorithm is the pivot strategy in [[median of medians]], while "median of medians" itself is the resulting quickselect algorithm, using the median as a pivot. In practice the overhead of median selection 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).
▲
== Incremental sorting by selection ==
| |||