Selection algorithm: Difference between revisions

Revision as of 15:14, 20 September 2013

Revision as of 00:08, 6 November 2013

Line 2:

In [[computer science]], a '''selection algorithm''' is an [[algorithm]] for finding the ''k''th smallest number in a [[List (abstract data type)|list]] or [[Array data structure|array]]; such a number is called the ''k''th ''[[order statistic]]''. This includes the cases of finding the [[minimum]], [[maximum]], and [[median]] elements. There are O(''n'') (worst-case linear time) selection algorithms, and sublinear performance is possible for structured data; in the extreme, O(1) for an array of sorted data. Selection is a subproblem of more complex problems like the [[nearest neighbor problem]] and [[shortest path]] problems. Many selection algorithms are derived by generalizing a [[sorting algorithm]], and conversely some sorting algorithms can be derived as repeated application of selection.

The simplest case of a selection algorithm is finding the minimum (or maximum) element by iterating through the list, keeping track of the running minimum (resp. maximum) – the minimum so far – (or maximum) and can be seen as related to the [[selection sort]]. Conversely, the hardest case of a selection algorithm is finding the median, and this necessarily takes ''n''/2 storage. In fact, a specialized median-selection algorithm can be used to build a general selection algorithm, as in [[median of medians]]. The best-known selection algorithm is [[quickselect]], which is related to [[quicksort]]; like quicksort, it has (asymptotically) optimal average performance, but poor worst-case performance, though it can be modified to give optimal worst-case performance as well.

== Selection by sorting ==