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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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.

1
2
3
4
5
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)