Selection algorithm: Difference between revisions

Revision as of 20:17, 10 August 2023

Revision as of 20:21, 10 August 2023

Line 9:

An algorithm for the selection problem takes as input a collection of values, and a {{nowrap|number <math>k</math>.}} It outputs the {{nowrap|<math>k</math>th}} smallest of these values, or, in some versions of the problem, a collection of the <math>k</math> smallest values. For this to be well-defined, it should be possible to [[Sorting|sort]] the values into an order from smallest to largest; for instance, they may be [[Integer (computer science)|integers]], [[floating-point number]]s, 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.{{r|cunmun}}

To simplify the problem, some variationsworks assumeon thatthis allproblem ofassume that the values are all distinct from each {{nowrap|other,{{r|clrs}}}} or that some consistent tie-breaking method has been used to assign an ordering to pairs of items with equalthe valuessame value as each other. ForAnother avariation completein the problem definition concerns the numbering of the problem,ordered values: is the choicesmallest betweenvalue twoobtained competingby {{nowrap|setting <math>k=0</math>,}} as in [[zero-based numbering]] of arrays, or is it obtained by {{nowrap|setting <math>k=1</math>,}} following the usual English-language conventions for obtaining 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 mustis beobtained made:from {{nowrap|<math>k=1</math>.{{r|clrs}}}}

#The smallest value is obtained by {{nowrap|setting <math>k=0</math>,}} as in [[zero-based numbering]] of arrays

#The smallest value is obtained by {{nowrap|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 by setting {{nowrap|<math>k=1</math>.{{r|clrs}}}}

In addition toWith these conventions, the maximum value, among a collection of <math>n</math> values, is obtained by {{nowrap|setting <math>k=n</math>.}} When <math>n</math> is an [[odd number]], the [[median]] of the collection is obtained by {{nowrap|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 {{nowrap|<math>k=n/2+1</math>.{{r|clrs}}}}

==Algorithms==