Question

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/
1 x D AOEp
2 i D p 1
3 j D r C 1
4 while TRUE
5 repeat
6 j D j 1
7 until AOEj x
8 repeat
9 i D i C 1
10 until AOEi x
11 if i < j
12 exchange AOEi with AOEj
13 else return j
a. Demonstrate the operation of HOARE-PARTITION on the array A D h13; 19; 9;
5; 12; 8; 7; 4; 11; 2; 6; 21i, 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 AOEp : : 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 AOEp : : r.
c. When HOARE-PARTITION terminates, it returns a value j such that p j < r.
d. Every element of AOEp : : j is less than or equal to every element of AOEj C1: : r
when HOARE-PARTITION terminates.
The PARTITION procedure in Section 7.1 separates the pivot value (originally
in AOEr) from the two partitions it forms. The HOARE-PARTITION procedure, on
the other hand, always places the pivot value (originally in AOEp) into one of the
two partitions AOEp : : j and AOEj C 1: : r. Since p j < r, this split is always
nontrivial.
e. Rewrite the QUICKSORT procedure to use HOARE-PARTITION.

Answer 1

a)

b)

In the first loop, i will terminate at the pivot, the smallest j would be the pivot, therefore no invalid position is accessed. In the next loops, i will finally terminate at last j and i will finally terminate at last i, and since and after the first loop, there is no change to access an element outside A[p…r].

c)

In b, we know the largest j in the first loop is r, while i will be at p, if then the loop will not terminate. In the second loop, jj has to move at least one step, therefore j must be less than r.

e)

def hoare_partition(a, p, r):
    x = a[p]
    i = p - 1
    j = r
    while True:
        while True:
            j -= 1
            if a[j] <= x:
                break
        while True:
            i += 1
            if a[i] >= x:
                break
        if i < j:
            a[i], a[j] = a[j], a[i]
        else:
            return j


def quicksort(a, p, r):
    if p < r - 1:
        q = hoare_partition(a, p, r)
        quicksort(a, p, q + 1)
        quicksort(a, q + 1, r)