Content deleted Content added
→Selection as incremental sorting: rewrite |
→Selection by sorting: elab unordered partial sorting |
||
Line 9:
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.
=== Unordered partial sorting ===
If partial sorting is relaxed so that the ''k'' smallest elements are returned, but not in order, the factor of O(''k'' log ''k'') can be eliminated. An additional maximum selection (taking O(''k'') time) is required, but since <math>k \leq n</math>, this still yields asymptotic complexity of O(''n'').
Conversely, given a selection algorithm, one can easily get an unordered partial sort (''k'' smallest elements, not in order) in O(''n'') time by iterating through the list and recording all elements less than the ''k''th element. If this results in fewer than ''k'' − 1 elements, any remaining elements equal the ''k''th element. Care must be taken, due to the possibility of equality of elements: one must not include all element less than ''or equal to'' the ''k''th element, as elements greater than the ''k''th element may also be equal to it.
Thus unordered partial sorting (lowest ''k'' elements, but not ordered) and selection of the ''k''th element are very similar problems. Not only do they have the same asymptotic complexity, O(''n''), but a solution to either one can be converted into a solution to the other by a straightforward algorithm (finding a max of ''k'' elements, or filtering elements of a list below a cutoff of the value of the ''k''th element).
=== Partial selection sort ===
| |||