Selection algorithm: Difference between revisions

Revision as of 20:50, 8 October 2014

Revision as of 06:23, 18 December 2014

Line 5:

== Selection by sorting ==

SelectionBy sorting the list or array then selecting the desired element, selection can be [[Reduction (complexity)|reduced]] to [[sorting algorithm|sorting]] by sorting the list or array and then selecting the desired element. This method is inefficient for selecting a single element, but is efficient when many selections need to be made from an array, in which case only one initial, expensive sort is needed, followed by many cheap selection operations – O(1) for an array, though selection is O(''n'') in a list, even if sorted, due to lack of [[random access]]. In general, sorting requires O(''n'' log ''n'') time, where ''n'' is the length of the list, although a lower bound is possible with non-comparative sorting algorithms like [[radix sort]] and [[counting sort]].

Rather than sorting the whole list or array, one can instead use [[partial sorting]] to select the ''k'' smallest or ''k'' largest elements. The ''k''th smallest (resp., ''k''th largest element) is then the largest (resp., smallest element) of the partially sorted list – this then takes O(1) to access in an array and O(''k'') to access in a list. This is more efficient than full sorting, but less efficient than simply selecting, and takes O(''n'' + ''k'' log ''k'') time, due to the sorting of the ''k'' elements. Partial sorting algorithms can often be derived from (total) sorting algorithms. As with total sorting, partial sorting means that further selections (below the ''k''th element) can be done in O(1) time for an array and O(''k'') time for a list. Further, if the partial sorting also partitions the original data into "sorted" and "unsorted", as with an in-place sort, the partial sort can be extended to a larger partial sort by only sorting the incremental portion, and if this is done, further selections above the ''k''th element can also be done relatively cheaply.