Selection algorithm: Difference between revisions

Revision as of 20:17, 10 August 2023

Latest revision as of 20:59, 28 January 2025

(14 intermediate revisions by 10 users not shown)

Line 1:

{{good article}}

{{Short description|Method for finding kth smallest value}}

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

{{goodGood article}}

{{Use mdy dates|cs1-dates=ly|date=April 2023}}

{{Use list-defined references|date=April 2023}}

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

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 {{nowrap|<math>k</math>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 <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 {{nowrap|time <math>O(1)</math>.}}

==Problem statement==

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 (computer science)|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 [[Relational operator|comparison operation]] that can determine the relative ordering of any two values, but may not perform any other kind of [[Arithmetic|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==

Line 63 ⟶ 60:

== Exact numbers of comparisons ==

[[File:Median of 5.svg|thumb|upright=0.9|Finding the median of five values using six comparisons. Each step shows the comparisons to be performed next as yellow line segments, and a [[Hasse diagram]] of the order relations found so far (with smaller=lower and larger=higher) as blue line segments. The red elements have already been found to be greater than three others and so cannot be the median. The larger of the two elements in the final comparison is the median.]]

[[Donald Knuth|Knuth]] supplies the following triangle of numbers summarizing pairs of <math>n</math> and <math>k</math> for which the exact number of comparisons needed by an optimal selection algorithm is known. The {{nowrap|<math>n</math>th}} row of the triangle (starting with <math>n=1</math> in the top row) gives the numbers of comparisons for inputs of <math>n</math> values, and the {{nowrap|<math>k</math>th}} number within each row gives the number of comparisons needed to select the {{nowrap|<math>k</math>th}} smallest value from an input of that size. The rows are symmetric because selecting the {{nowrap|<math>k</math>th}} smallest requires exactly the same number of comparisons, in the worst case, as selecting the {{nowrap|<math>k</math>th}} {{nowrap|largest.{{r|knuth}}}}

{{center|0}}

Line 81 ⟶ 78:

Very few languages have built-in support for general selection, although many provide facilities for finding the smallest or largest element of a list. A notable exception is the [[Standard Template Library]] for [[C++]], which provides a templated <code>nth_element</code> method with a guarantee of expected linear time.{{r|skiena}}

[[Python (programming language)|Python]]'s standard library (since 2.4) includes <code>heapq.nsmallest</code> and <code>heapq.nlargest</code> subroutinesfunctions for returning the smallest or largest elements from a collection, in sorted order. Different versions of Python have used different algorithms for these subroutines. As of Python version 3.13, theThe implementation maintains a [[binary heap]], limited to holding <math>k</math> elements, and initialized to the first <math>k</math> elements in the collection. Then, each subsequent itemsitem of the collection may replace the largest or smallest element in the heap (respectivelyif forit <code>heapqis smaller or larger than this element.nsmallest</code> andThe algorithm's memory usage is superior to heapselect (the former only holds <codemath>heapq.nlargestk</codemath>) ifelements itin ismemory smallerat ora largertime thanwhile thisthe elementlatter requires manipulating the entire dataset into memory). The worst-caseRunning time fordepends thison implementationdata ordering. The best case is <math>O((n - k) + k\log k)</math>, worsefor thanalready thesorted data. The worst-case is <math>O(n+k\log nk)</math> thatfor wouldreverse be achievedsorted by heapselectdata. However,In for randomaverage input sequencescases, there are likely to be few heap updates and most input elements are processed with only a single comparison. For example, extracting the 100 largest or smallest values out of 10,000,000 random inputs makes 10,009,401 comparisons on average.{{r|python}}

Since 2017, [[Matlab]] has included <code>maxk()</code> and <code>mink()</code> functions, which return the maximal (minimal) <math>k</math> values in a vector as well as their indices. The Matlab documentation does not specify which algorithm these functions use or what their running {{nowrap|time is.{{r|matlab}}}}

Line 130 ⟶ 127:

| publisher = Association for Computing Machinery

| title = Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6–8, 1985, Providence, Rhode Island, USA

| year = 1985}}</ref>| doi-access = free

| isbn = 0-89791-151-2

}}</ref>

<ref name=bfprt>{{cite journal

Line 174 ⟶ 173:

| title = Space-Efficient Data Structures, Streams, and Algorithms – Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday

| volume = 8066

| year = 2013| isbn = 978-3-642-40272-2 }}</ref>

<ref name=brown>{{cite journal

Line 213 ⟶ 212:

| title = Mathematical Foundations of Computer Science 1993, 18th International Symposium, MFCS'93, Gdansk, Poland, August 30 – September 3, 1993, Proceedings

| volume = 711

| year = 1993}}<| hdl = 11858/ref>00-001M-0000-0014-B748-C

| isbn = 978-3-540-57182-7

| hdl-access = free

}}</ref>

<ref name=clrs>{{Introduction to Algorithms|edition=3|chapter=Chapter 9: Medians and order statistics|pages=213–227}}; "Section 14.1: Dynamic order statistics", pp. 339–345</ref>

Line 240 ⟶ 242:

| volume = 36

| year = 1989| s2cid = 10947879

| doi-access = free

}}</ref>

Line 314 ⟶ 317:

| s2cid = 3064709

| title = Expected time bounds for selection

| volume = 18| doi-access = free

| volume = 18}} See also "Algorithm 489: the algorithm SELECT—for finding the {{nowrap|<math>i</math>th}} smallest of <math>n</math> elements", p. 173, {{doi|10.1145/360680.360694}}.</ref>

<ref name=frederickson>{{cite journal

Line 325 ⟶ 329:

| title = An optimal algorithm for selection in a min-heap

| volume = 104

| year = 1993}}</ref>| doi-access = free

}}</ref>

<ref name=frejoh>{{cite journal

Line 399 ⟶ 404:

| volume = 40

| year = 1993| s2cid = 17956460

| doi-access = free

}}</ref>

Line 416 ⟶ 422:

| title = 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8–9, 2019, San Diego, CA, USA

| volume = 69

| year = 2019}}</ref>| doi-access = free

}}</ref>

<ref name=kletar>{{cite book

Line 470 ⟶ 477:

| publisher = IEEE Computer Society

| title = 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18–21, 2014

| year = 2014| isbn = 978-1-4799-6517-5 }}</ref>

<ref name=prt>{{cite journal

Line 484 ⟶ 491:

| volume = 26

| year = 1983| s2cid = 3211474

| doi-access = free

}}</ref>