Begin = first position in array to be partitioned
End   =  last position in array to be partitioned

PivPos = random_in_range(Begin, End)
Piv    = A[PivPos]

P = Begin
Q = End

while (true)
{
  // move P forward over anything <= pivot
  while  A[P] <= Piv  and  P <= End
    P += 1

  // move Q backward over anything >= pivot
  while  A[Q] >= Piv  and  Q >= Begin
    Q -= 1

  if  P < Q
  {
    // we haven't finished yet
    swap(A[P], A[Q])
    P += 1
    Q -= 1 }
  else
  { 
    // we have finished, but note that the pivot will never
    // have moved, we still know where it is, so we can now
    // move it in between P and Q, and shrink one of the
    // partitions a little bit
    if  P <= PivPos
    { swap(A[P], A[PivPos])
      P += 1 }
    else if  Q >= PivPos
    { swap(A[Q], A[PivPos])
      Q += 1 }
    break
  }
}


All that's left to do is recursively:
   Quicksort between A[begin] and A[Q]
   Quicksort between A[P] and A[end]

It is guaranteed that the total amount left to be sorted
is less than the total amount before partitioning started

So even if we pick the worst possible pivot every time,
progress will still be made, and sorting will finish in
quadratic time, instead of the more usual nice N log N.