[prev] 27 [next]

Randomised Quicksort

partition(array,low,high):
|  Input  array, index range low..high
|  Output randomly select a pivot element from array[low..high]
|         moves all smaller elements between low..high to its left
|         moves all larger elements between low..high to its right
|         returns new position of pivot element
|
|  randomly select pivot_index∈[low..high]
|  pivot_item=array[pivot_index], swap array[low] with array[pivot_index]
|  left=low+1, right=high
|  while left<right do
|  |  left  = find index of leftmost element > pivot_item    // left=high if none
|  |  right = find index of rightmost element <= pivot_item
|  |  if left<right then
|  |     swap array[left] with array[right]
|  |  end if
|  end while
|  array[low] = array[right], array[right]=pivot_item
|  return right