Content deleted Content added
(correct changes from Revision as of 03:02, 18 April 2011 |
→Partition-based general selection algorithm: pivotDist should be calculated based on left bound |
||
Line 46:
''// Returns the k-th smallest element of list within left..right inclusive.''
'''function''' select(list, left, right, k)
'''if''' left = right ''// If the list contains only one element''
'''return''' list[left] ''// Return that element''
pivotIndex := ... ''// select a pivotIndex between left and right''
pivotNewIndex := partition(list, left, right, pivotIndex)
pivotDist := pivotNewIndex - left + 1
''// The pivot is in its final sorted position,''
''// so pivotDist reflects its 1-based position if list were sorted''
'''if''' pivotDist = k
'''return''' list[pivotNewIndex]
'''else if''' k < pivotDist
'''return''' select(list, left, pivotNewIndex - 1, k)
'''else'''
'''return''' select(list, pivotNewIndex + 1, right, k - pivotDist)
Note the resemblance to quicksort: 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 [[in-place algorithm]], requiring only constant memory overhead, since the [[tail recursion]] can be eliminated with a loop like this:
| |||