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)

a.?Demonstrate the operation of HOARE-PARTITION on the array A = ?13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21?, 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:

b.?The indices?i?and?j?are such that we never access an element of?A?outside the subarray?A[p . . r].

c.?When HOARE-PARTITION terminates, it returns a value j such that p ? j

d.?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 partitions A[p . . j] and A[j + 1. . r]. Since p ? j

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

1 x = A[p] 2 i = p-1 3 j =r +1 4 while TRUE repeat j = j 1 until A[j] < x 7 8 repeat i = i +1 until A[i] > x if i < j exchange A[i] with A[j] else return j 10 11 12 13