Content deleted Content added
Wikicode, corrections |
m Bold |
||
Line 39:
minValue = a[j]
swap a[i] and a[minIndex]
'''return''' a[k]
Other advantages of this method are:
Line 70:
'''return''' a[k]
'''else if''' k < pivotNewIndex
'''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:
| |||