Selection algorithm

In computer science, a selection algorithm is an algorithm for finding the ${\displaystyle k}$th smallest value in a collection of ordered values, such as numbers. The value that it finds is called the ${\displaystyle k}$th order statistic. Selection includes as special cases the problems of finding the minimum, median, and maximum element in the collection. Selection algorithms include quickselect, and the median of medians algorithm. When applied to a collection of ${\displaystyle n}$ values, these algorithms take linear time, ${\displaystyle O(n)}$ as expressed using big O notation. For data that is already structured, faster algorithms may be possible; as an extreme case, selection in an already-sorted array takes time ${\displaystyle O(1)}$.