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
|