Chapter 7, Problem 1P

(a)

Program Plan Intro

To show that the values of array and auxiliary values after each iterations of while loop using HOARE-PARTITION.

Explanation of Solution

Given Information: The array is $A[]=\{13,19,9,5,12,8,7,4,11,2,6,21\}$.

Explanation: According to the HOARE-PARTITION, algorithm $p=1$ and $r=12$ so the while loop run from 1 to 12.

Consider that $x=13$ is pivot element.

Now the array and auxiliary after each pass through HOARE-PARTITION algorithm will show in below table-

After the iteration $p=4$ , the elements which is greater than pivot element( $x=13$ ) is placed in their suitable place then the partition pass stop and show the final result of partition as shown in below-

Hence, the HOARE-PARTITION algorithm exit the while loop with the auxiliary values of $i=10$ and $j=2$ .

(b)

Program Plan Intro

To showthat the indices i and j are such that we never access an element of array A outside the sub-array.

Explanation of Solution

In the beginning of while loop when $\left|A\right|\ge 2$ then the condition $i>j$ will be true.

Consider that it has an element k and $k>i$ that means that $A[k]\ge x$ and $k\text{'}<j$ that is $A[j\text{'}]\le x$ this proves that I and j are outside the bounds of array and element x must lies in between the two as $i>j$

If it takes parameter $k=j$ and $k\text{'}=i$ then the element j was in the position of element i in the next iterations of loop that proves that the element k fulfill the relation of x that is $A[k]\ge x$ .

Hence, it is can be concluded that the indices i and j are such that one never access an element of array A outside the sub-array.

(c)

Program Plan Intro

To explain that when HOARE-PARTITION terminates, it returns a value j such that $p\le j<r$ .

Explanation of Solution

The value of jis decreased after every iteration and at the final iteration of the loop i will equals to 1but greater than r .

Line 11 of HOARE-PARTITION illustrate that $i=1$ because in the array $A[p]=x\ge x$ so the HOARE-PARTITION algorithm terminates and at that time $j=1$ and $p>1$ .

Therefore, the HOARE-PARTITION algorithm terminates and returns $j=1>p$ .

(d)

Program Plan Intro

To explain that the every element of array is less than or equal to every element of $A[j+\mathrm{1...}r]$ , when HOARE-PARTITION algorithm terminates.

Explanation of Solution

Consider that it just finished the iteration of the loop in which j went to j₁ and j₂ and I went to i₁ to i₂ . The elements of the array $A[i+\mathrm{1......}i-1]$ are less than x as defined in the algorithm from line 8 to line 10.

Similarly, the elements of the array $A[j+\mathrm{1....}j-1]$ are less than x as defined in the algorithm so the condition of array will be $A[i]\le x\le A[j]$ after the exchange of line 12. Since all the elements of $A[j\mathrm{......}r]$ is greater than or equal to x.

Now putting all the conditions of the array defined in the algorithm it has condition that is $A[p\mathrm{......}i]=A[p\mathrm{.....}i1]\cup A[p\mathrm{.....}i2]\cup \mathrm{........}\cup A[p\mathrm{....}r]$ .

Since at the termination of the algorithm $i\ge j$ which implies that $A[p\mathrm{...}j]\subseteq A[p\mathrm{...}i]$ that means that every elements of array $A[p\mathrm{..}j]$ is less than or equal to x and x is less than or equal to the every element of $A[j+\mathrm{1...}r]\subseteq A[j\mathrm{...}r]$ .

Therefore, the every element of array $A[p\mathrm{..}j]$ is less than or equal to every element of $A[j+\mathrm{1...}r]$ when HOARE-PARTITION algorithm terminates.

(e)

Program Plan Intro

To rewrite the QUICK-SORT procedure by using HOARE-PARTITION algorithm.

Explanation of Solution

QUICKSORT(A,p,r).
	If   then
		q =HOARE-PARTITION(A,p,r).
		QUICKSORT(A,p,q-1).
		QUICKSORT(A,q+1,r).
	End if.

HOARE-PARTITION(A,p,r)
	 
	while TRUE
		repeat
			 
		until .
		repeat 
			 .
		until .
		if  then
			exchange  with .
		else return j.
		end if.
	end while.

The quick sort algorithm is based on recursion. It first sets the parameters and then check the initial condition.

If the initial condition is true then it call the HOARE-PARTITION algorithm with recursion of calling itself again and again until the initial condition becomes false.