Content deleted Content added
No edit summary |
m Reverted edits by 67.101.161.204 to last version by 137.111.13.34 |
||
Line 72:
'''return''' select(a, k, left, pivotNewIndex-1)
'''else'''
'''return''' select(a, k-(pivotNewIndex+1), pivotNewIndex+1, right)
Note the resemblance 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 overhead, since the tail recursion can be eliminated with a loop like this:
Line 86:
'''else'''
left := pivotNewIndex+1
k := k - (pivotNewIndex+1)
Like quicksort, the performance of the algorithm is sensitive to the pivot that is chosen. If bad pivots are consistently chosen, this degrades to the minimum-based selection described previously. However, there is a way to consistently find very good pivots; this is the key to making the algorithm worst-case linear.
| |||