Content deleted Content added
m add pseudo-assignment to disambiguate "comment". improve formatting of comments. |
|||
Line 45:
In quicksort, we recursively sort both branches, leading to best-case [[Big-O notation|Ω]](''n'' log ''n'') time. However, when doing selection, we already know which partition our desired element lies in, since the pivot is in its final sorted position, with all those preceding it in sorted order and all those following it in sorted order. Thus a single recursive call locates the desired element in the correct partition:
''// 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]
Line 64 ⟶ 65:
'''function''' select(list, left, right, k)
'''loop'''
pivotIndex := ... ''// select pivotIndex between left and right''
pivotNewIndex := partition(list, left, right, pivotIndex)
pivotDist := pivotNewIndex - left + 1
| |||