Selection algorithm: Difference between revisions

Revision as of 16:23, 26 March 2004

Revision as of 16:26, 26 March 2004

Line 1:

In [[computer science]], a '''selection algorithm''' is aan mechanical method[[algorithm]] of finding the ''k''th smallest number in a list. This includes the simple common cases of finding the minimum, maximum, and median elements.

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 only need 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.