# 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 j


a. 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.

HOARE-QUICKSORT(A, p, r)
if p < r
q = HOARE-PARTITION(A, p, r)
HOARE-QUICKSORT(A, p, q)
HOARE-QUICKSORT(A, q + 1, r)