Content deleted Content added
Order statistics |
Add sorting as real method used before table of contents |
||
Line 1:
In [[computer science]], a '''selection algorithm''' is an [[algorithm]] for finding the ''k''th smallest (or ''k''th largest) number in a list. This includes the simple common cases of finding the minimum, maximum, and median elements. These are also called order statistics.
== Selection with sorting algorithm ==
One simple and widely used selection algorithm is to use a [[sort algorithm]] on the list, and then extract the ''k''th element. This is particularly useful when we wish to make many different selections from a single list, in which case only one initial, expensive sort is needed, followed by many cheap extraction operations. When we need only to perform one selection, however, or when we need to strongly mutate the list between selections, this method can be costly, typically requiring at least O(''n'' log ''n'') time, where ''n'' is the length of the list.
| |||