Content deleted Content added
Add sublinear selection improvement data structure information |
Order statistics |
||
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.
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.
| |||