Content deleted Content added
m or kth largest |
Noted advantages of minimum-based method and added section Selection as incremental sorting |
||
Line 44:
return a[k]
</pre>
Other advantages of this method are:
* After locating the ''j''th smallest element, it requires only O(''j'' + (''k''-''j'')<sup>2</sup>) time to find the ''k''th smallest element, or only O(''k'') for ''k'' ≤ ''j''.
* It can be done with [[linked list]] data structures, whereas the one based on partition requires [[random access]].
==Linear general selection algorithms==
Line 108 ⟶ 112:
In practice, although this approach optimizes quite well, it is still typically outperformed by a considerable margin by the expected linear algorithm with fairly naive pivot choices, such as choosing one randomly.
The worst-case algorithm still has importance, however; it can be used, for example, to construct a worst-case O(''n'' log ''n'') quicksort algorithm, by using it to find the median at every step.
== Selection as incremental sorting ==
One of the advantages of the sort-and-index approach, as mentioned, is its ability to [[amortized analysis|amortize]] the sorting cost over many subsequent selections. However, sometimes the number of selections that will be done is not known in advance, and may be either small or large. In these cases, we can adapt the algorithms given above to simultaneously select an element while partially sorting the list, thus accelerating future selections.
Both the selection procedure based on minimum-finding and the one based on partitioning can be seen as a form of partial sort. The minimum-based algorithm sorts the list up to the given index, and so clearly speeds up future selections, especially of smaller indexes. The partition-based algorithm does not achieve the same behaviour automatically, but can be adapted to remember its previous pivot choices and reuse them wherever possible, avoiding costly partition operations, particularly the top-level one. The list becomes gradually more sorted as more partition operations are done incrementally; no pivots are ever "lost." If desired, this same pivot list could be passed on to quicksort to reuse, again avoiding many costly partition operations.
== References ==
| |||