Selection algorithm: Difference between revisions

Revision as of 20:56, 1 April 2023

Revision as of 20:58, 1 April 2023

Line 1:

{{Short description|An algorithmMethod for finding the kth smallest number in a list or arrayvalue}}

{{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>.}}