7-1 Hoare partition correctness¶

The version of PARTITION given in this chapter is not the original partitioning algorithm. Here is the original partitioning 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 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 the indices $i$ and $j$ after each iteration of the while loop in lines 4313.

b. Describe how the PARTITION procedure in Section 7.1 differs from HOARE-PARTITION when all elements in $A[p:r]$ are equal. Describe a practical advantage of HOARE-PARTITION over PARTITION for use in quicksort.

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:

c. The indices $i$ and $j$ are such that the procedure never accesses an element of $A$ outside the subarray $A[p:r]$

d. When HOARE-PARTITION terminates, it returns a value $j$ such that $p \leq j < r$.

e. 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\leq j < r$, neither partition is empty.

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

7-1 Hoare partition correctness¶

a¶