7-1 Hoare partition correctness
The version of $\text{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 ja. Demonstrate the operation of $\text{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 $\text{HOARE-PARTITION}$ is correct. Assuming that the subarray $A[p..r]$ contains at least two elements, prove the following:
b. The indices $i$ and $j$ are such that we never access an element of $A$ outside the subarray $A[p..r]$.
c. When $\text{HOARE-PARTITION}$ terminates, it returns a value $j$ such that $p \le j < r$.
d. Every element of $A[p..j]$ is less than or equal to every element of $A[j + 1..r]$ when $\text{HOARE-PARTITION}$ terminates.
The $\text{PARTITION}$ procedure in section 7.1 separates the pivot value (originally in $A[r]$) from the two partitions it forms. The $\text{HOARE-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.
e. Rewrite the $\text{QUICKSORT}$ procedure to use $\text{HOARE-PARTITION}$.
a. After the end of the loop, the variables have the following values: $x = 13$, $j = 9$ and $i = 10$.
b. Because when $\text{HOARE-PARTITION}$ is running, $p \le i < j \le r$ will always hold, $i$, $j$ won't access any element of $A$ outside the subarray $A[p..r]$.
c. When $i \ge j$, $\text{HOARE-PARTITION}$ terminates, so $p \le j < r$.
d. When $\text{HOARE-PARTITION}$ terminates, $A[p..j] \le x \le A[j + 1..r]$.
e.