Selection algorithm: Difference between revisions

Revision as of 23:20, 29 March 2023

Revision as of 23:39, 29 March 2023

Line 2:

{{for|simulated natural selection in genetic algorithms|Selection (genetic algorithm)}}

{{more footnotes|date=July 2017}}

In [[computer science]], a '''selection algorithm''' is an [[algorithm]] for finding the <math>k</math>th smallest value in a collection of ordered values, such as numbers. The value that it finds is called the <math>k</math>th [[order statistic]]. ForSelection aincludes collectionas ofspecial <math>n</math>cases values,the setting <math>k</math> to <math>1</math>, <math>(n+1)/2</math> (with some choiceproblems of rounding), or <math>n</math> producesfinding the [[minimum]], [[median]], and [[maximum]] elementselement in the given collection, respectively.{{r|clrs}} Selection algorithms include [[quickselect]], and the [[median of medians]] algorithm. When applied to a collection of <math>n</math> values, these algorithms take [[linear time]], <math>O(n)</math> 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 (data structure)|array]] takes time <math>O(1)</math>.

==Problem statement==

An algorithm for the selection problem takes as input a collection of values, and a number <math>k</math>. It outputs the <math>k</math>th smallest of these values.

For this should be well-defined, it should be possible to [[Sorting|sort]] the values into an order from smallest to largest; for instance, they may be numbers, or some other kind of object with a numeric key. However, they are not assumed to have been already sorted. Often, selection algorithms are restricted to a comparison-based [[model of computation]], as in [[comparison sort]] algorithms, where the algorithm has access to a comparison operation that can determine the relative ordering of any two values, but may not perform any other kind of arithmetic operations on these values.

To simplify the problem, some sources may assume that the values are all distinct from each other,{{r|clrs}} or that some consistent tie-breaking method has been used to order items with the same value as each other. Another variation in the problem definition concerns the numbering of the ordered values: is the smallest value obtained by setting <math>k=0</math>, as in [[zero-based numbering]] of arrays, or is it obtained by setting <math>k=1</math>, following the usual English-language conventions for the smallest, second-smallest, etc.? This article follows the conventions used by Cormen et al., according to which all values are distinct and the minimum value is obtained from <math>k=1</math>.{{r|clrs}}

With these conventions, the maximum value, among a collection of <math>n</math> values, is obtained by setting <math>k=n</math>. When <math>n</math> is an [[odd number]], the [[median]] of the collection is obtained by setting <math>k=(n+1)/2</math>. When <math>n</math> is even, there are two choices for the median, obtained by rounding this choice of <math>k</math> down or up, respectively: the ''lower median'' with <math>k=n/2</math> and the ''upper median'' with <math>k=n/2+1</math>.{{r|clrs}}

==Algorithms==