The version of
PARTITION
given in this chapter is not the original partitioning algorithm. Here is the original partition algorithm, which is due to C.A.R. Hoare:HOARE-PARTITION(A, p, r) x = A[p] i = p - 1 j = r + 1 while TRUE repeat j = j - 1 until A[j] ≤ x repeat i = i + 1 until A[i] ≥ x if i < j exchange A[i] with A[j] else return j
- Demonstrate the operation of
HOARE-PARTITION
on the array $A = \langle 13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21 \rangle$, showing the values of the array and auxiliary values after each iteration of the while loop in lines 4-13.The next three questions ask you to give a careful argument that the procedure
HOARE-PARTITION
is correct. Assuming that the subarray $A[p..r]$ contains at least two elements, prove the following:
- The indices $i$ and $j$ are such that we never access an element of $A$ outside the subarray $A[p..r]$.
- When
HOARE-PARTITION
terminates, it returns a value $j$ such that $p \le j < r$.- Every element of $A[p..j]$ is less than or equal to every element of $A[j + 1..r]$ when
HOARE-PARTITION
terminates.The
PARTITION
procedure in section 7.1 separates the pivot value (originally in $A[r]$) from the two partitions it forms. TheHOARE-PARTITION
procedure, on the other hand, always places the pivot value (originally in $A[p]$) into one of the two parititions $A[p..j]$ and $A[j + 1..r]$. Since $p \le j < r$, this split is always nontrivial.
- Rewrite the
QUICKSORT
procedure to useHOARE-PARTITION
.
At the end of the loop, the variables have the following values:
x = 13
j = 9
i = 10
The indices will not walk of the array. At the first check $i < j$, $i = p$ and $j \ge p$ (because $A[p] = x$). If $i = j$, the algorithm will terminate without accessing "invalid" elements. If $i < j$, the next loop will also have indices $i$ and $j$ within the array, (because $i \le r$ and $j \ge p$). Note that if one of the indices gets to the end of the array, then $i$ won't be less or equal to $j$ any more.
As for the return value, it will be at least one less than $j$. At the first iteration, either (1) $A[p]$ is the maximum element and then $i = p$ and $j = p < r$ or (2) it is not and $A[p]$ gets swapped with $A[j]$ where $j \le r$. The loop will not terminate and on the next iteration, $j$ gets decremented (before eventually getting returned). Combining those two cases we get $p \le j < r$.
Finally, it's easy to observe the following invariant:
Before the condition comparing $i$ to $j$, all elements $A[p..i-1] \le x$ and all elements $A[j+1..r] \ge x$.
Initialization. The two repeat blocks establish just this condition.
Maintenance. By exchanging $A[i]$ and $A[j]$ we make the $A[p..i] \le x$ and $A[j..r] \ge x$. Incrementing $i$ and decrementing $j$ maintain this invariant.
Termination. The loop terminates when $i \ge j$. The invariant still holds at termination.
The third bit follows directly from this invariant.
There's some C code below.
#include <stdbool.h> int hoare_partition(int A[], int p, int r) { int x = A[p], i = p - 1, j = r, tmp; while(true) { do { j--; } while (!(A[j] <= x)); do { i++; } while (!(A[i] >= x)); if (i < j) { tmp = A[i]; A[i] = A[j]; A[j] = tmp; } else { return j; } } } void quicksort(int A[], int p, int r) { if (p < r - 1) { int q = hoare_partition(A, p, r); quicksort(A, p, q + 1); quicksort(A, q + 1, r); } }