# Problem 7.1

## Hoare partition correctness

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

1. 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:

1. The indices $i$ and $j$ are such that we never access an element of $A$ outside the subarray $A[p..r]$.
2. When HOARE-PARTITION terminates, it returns a value $j$ such that $p \le j < r$.
3. 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. The 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.

1. Rewrite the QUICKSORT procedure to use HOARE-PARTITION.

### Demonstration

At the end of the loop, the variables have the following values:

x = 13
j = 9
i = 10


### Correctness

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.

### Implementation

There's some C code below. ### C code

#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);
}
}