Selection As Incremental Sorting
One of the advantages of the sort-and-index approach, as mentioned, is its ability to 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.
Read more about this topic: Selection Algorithm
Famous quotes containing the word selection:
“Judge Ginsburg’s selection should be a model—chosen on merit and not ideology, despite some naysaying, with little advance publicity. Her treatment could begin to overturn a terrible precedent: that is, that the most terrifying sentence among the accomplished in America has become, “Honey—the White House is on the phone.””
—Anna Quindlen (b. 1952)