Content deleted Content added
Noted advantages of minimum-based method and added section Selection as incremental sorting |
m link in-place |
||
Line 82:
</pre>
Note the resemblence to quicksort; indeed, just as the minimum-based selection algorithm is a partial selection sort, this is a partial quicksort, generating and partitioning only O(log ''n'') of its O(''n'') partitions. This simple procedure has expected linear performance, and, like quicksort, has quite good performance in practice. It is also an [[work-in-place|in-place]] algorithm, requiring only constant memory, since the tail recursion can be eliminated with a loop like this:
<pre>
| |||