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
|  repeat
|  |  right = find index of rightmost element <= pivot_item
|  |  left  = find index of leftmost element > pivot_item    // left=right if none
|  |  if left<right then
|  |     swap array[left] with array[right]
|  |  end if
|  until left≥right
|  if low<right then
|     swap array[low] with array[right]       // right is final position for pivot
|  end if
|  return right