In
computer science, a
selection algorithm is an
algorithm for finding the
kth smallest number in a
list or
array; such a number is called the
kth
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 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.