Content deleted Content added
m Replace magic links with templates per local RfC and MediaWiki RfC |
Added {{more footnotes}} tag to article (TW) |
||
Line 1:
{{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 ''k''th smallest number in a [[List (abstract data type)|list]] or [[Array data structure|array]]; such a number is called the ''k''th ''[[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 problem|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.
| |||