Partition(A, p, r)                /* O(n) */
1  x = A[r]
2  i = p - 1
3  for j = p to r - 1
4      if A[j] <= x
5          i = i + 1
6          A[i] を A[j] と交換する 
7  A[i+1] を A[r] と交換する 
8  return i + 1



Partition(A, p, r) の例:

Quicksort(A, p, r)
1  if p < r
2      q = Partition(A, p, r)
3      Quicksort(A, p, q - 1)
4      Quicksort(A, q + 1, r)