Content deleted Content added
→Selection by sorting: elab unordered partial sorting |
→Partition-based selection: selection and sorting |
||
Line 41:
* [[Median of medians]]
* [[Introselect]] ([[Introsort]])
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.
== Incremental sorting by selection ==
| |||