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 = A[p]
2 i = p-1
3 j = r + 1
4 while TRUE
5 repeat
6 j = j-1
7 until A[j] $ \leq$ x
8 repeat
9 i = i - 1
10 until A[E] $\geq$ x
11 if i < j
12 exchange A[i] with A[j]
13 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 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 \leq j < r$.
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 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 A[p..j] and A[j+1..r] . Since $p \leq j < r$, this split is always nontrivial.
e. Rewrite the QUICKSORT procedure to use HOARE-PARTITION.

a. Its important to understand until in the algorithm to solve this. Until means you have to do the opposite comparison if you write an actual program. so for $\leq$ we have to use $\gt$ and for $\leq$ we have to use $\gt$. We need use this while solving a.
for the first iteration x = 13 j =12
a[12] = 21 > 13
j = 11
since a[11] = 6 > 13 (false)
i = 1
a[1] = 13 < 13 (false)
swap a[1] and a[12]
the array will be A {6, 19, 9,5, 12, 8, 7, 4, 11, 2,13 , 21} for second iteration (i = 1 and j = 11):
j = 10
a[10] = 2 > 13 (false)
i = 2
a[2] = 19 < 13 (false)
swap a[2] and a[10]
the array will be A {6, 2, 9,5, 12, 8, 7, 4, 11, 19,13 , 21}
for third iteration(i = 2 and j = 10):
j = 9 a[9] = 11 > 13(false)
i = 3
a[3] = 9 < 13
i = 4
a[4] = 5 < 13
i = 5
a[5] = 12 < 13
i = 6
a[6] = 8 < 13
i = 7
a[7] = 7 < 13
i =8
a[8] = 4 < 13
i = 9
a[9] = 11 < 13
i = 10
a[10] = 2 < 13
i = 11
a[11] = 19 < 13 (false)
since i > j the loop will be terminated and we return j = 9.
b. we never access any element outside the Subaaray A[p..r] because we begin with j = j -1 and decremented before accessing any element outside r. similarly we begin with i = p -1 and increment it before any element outside p and the loop terminates when i > j so i will not go past r.
At the begging k =1 i = p and $p \leq j \leq r$. At k > 1 iteration $p \leq i \leq j \lt r$ . At k+1 iteration $p \leq i \lt i' \lt j' \leq j \lt r$. If the loop terminates at k th iteration we have $p \leq i \leq i' \leq j' \leq j \lt r$. So no element outside A[p..r] will be accessed.

k = 1
i					j
p	.	.	.	.	q
k > 1(k iteration)
	i			j
p	.	.	.	.	q
k+1 iteration
	i	i'	j'
p	.	.	.	.	q

c. from above we can prove $p \leq j \lt r$.
d. After kth iteration the elements A[p..i] $\leq$ x and the elements A[j..r] $\geq$ x. After the while loop termination all the elements A[p..j] will be less than or equal to A[j+1..r].
e. We cannot use the same logic as in PARTITION AND QUICK-SORT and HOARE-PARTITION and QUICK-SORT because in PARTITION and QUICK-SORT the pivot is in fixed position and we don't use pivot in the next iteration as we know all the elements to left of pivot are less than pivot and all elements to right are greater than pivot. IN HOARE-PARTITION the algorithm uses pivot for comparison but we don't get the similar sub array as in PARTITION and QUICK-SORT.
QUICKSORT(A,p,r)
if(p q = HOARE-PARITION(A,p,r)
QUICKSORT(A,p,q)
QUICKSORT(A,q+1,r)