$2.(6$ points$)$ The version of PARTITION discussed in lecture is not the original partitioning algorithm. Here is the original

partition algorithm, which is due to T$.$ Hoare:

HOARE$-$PARTITION$($A$,$ p$,$ r$)$

$1$ x $$ A$[$p$]$

$2$ i $$ p $-1$

$3$ j $$ r $+1$

$4$ while TRUE

$5$ do repeat j $$ j $-1$

$6$ until A$[$j$]<=$ x

$7$ repeat i $$ i $+1$

$8$ until A$[$i$]>=$ x

$9$ if i $<$ j

$10$ then exchange A$[$i$]$ A$[$j$]$

$11$ else return j

$2$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 loop in lines $411.$

The next three questions ask you to give a careful argument that the procedure HOARE$-$PARTITION is correct. Prove the

following:

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

$2$c$)$ When HOARE$-$PARTITION terminates, it returns a value j such that p $<=$ j $<$ r$.$

$2$d$)$ Every element of A$[$p $..$ j$]$ is less than or equal to every element of A$[$j $+1..$ r$]$ when HOARE$-$PARTITION

terminates.