Content deleted Content added
→Language support: C++ nth_element has been mentioned twice. |
→Selection by sorting: Remove apparently non-sense text. There isn't any O(n + k log k) worst-case algorithm for partial sorting, and this text is claiming that isn't even as efficient as "simply selecting".. |
||
Line 7:
By sorting the list or array then selecting the desired element, selection can be [[Reduction (complexity)|reduced]] to [[sorting algorithm|sorting]]. 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 linked 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
=== Unordered partial sorting ===
Line 33:
swap list[i] and list[minIndex]
'''return''' list[k]
== Partition-based selection ==
{{further|Quickselect}}
| |||