In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list (such a number is called the kth order statistic). This includes the cases of finding the minimum, maximum, and median elements. There are worst-case linear time selection algorithms. Selection is a subproblem of more complex problems like the nearest neighbor problem and shortest path problems.
The term "selection" is used in other contexts i...
more
In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list (such a number is called the kth order statistic). This includes the cases of finding the minimum, maximum, and median elements. There are worst-case linear time selection algorithms. Selection is a subproblem of more complex problems like the nearest neighbor problem and shortest path problems.
The term "selection" is used in other contexts in computer science, including the stage of a genetic algorithm in which genomes are chosen from a population for later breeding; see Selection (genetic algorithm). This article addresses only the problem of determining order statistics.
Selection can be reduced to sorting by sorting the list and then extracting the desired element. This method is efficient when many selections need to be made from a list, in which case only one initial, expensive sort is needed, followed by many cheap extraction operations. In general, this method requires ...
less
