Selection algorithm: Difference between revisions

Revision as of 23:34, 8 April 2013

Revision as of 17:21, 9 April 2013

Line 96:

The ''Select'' algorithm divides the list into groups of five elements. (Left over elements are ignored for now.) Then, for each group of five, the median is calculated (an operation that can potentially be made very fast if the five values can be loaded into [[Processor register|registers]] and compared). (If sorting in-place, then these medians are moved into one contiguous block in the list.) ''Select'' is then called recursively on this sublist of ''n''/5 elements to find their true median. Finally, the "median of medians" is chosen to be the pivot.

''//returns the index of the median of medians.''

''//requires a variant of select, "selectIdx"''
''//which returns the index of the selected item rather than the value''

'''function''' medianOfMedians(list, left, right)

numMedians = (right - left) / 5

'''for''' i '''from''' 0 '''to''' numMedians

'''//get the median of the five-element subgroup'''

subLeft := left + i*5

subRight := subLeft + 4

if (subRight > right) subRight := right

'''//alternatively, use a faster method that works on lists of size 5'''

medianIdx := selectIdx(list, subLeft, subRight, (subRight - subLeft) / 2)

'''//move the median to a contiguous block at the beginning of the list'''

swap list[left+i] and list[medianIdx]

'''//select the median from the contiguous block'''

'''return''' selectIdx(list, left, left + numMedians, numMedians / 2)