The version of PARTITION given in this chapter is not the original partitioning
ID: 672518 • Letter: T
Question
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: 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: The indices i and j are such that we never access an element of A outside the subarray A[p. .r}. When HOARE-PARTITION terminates, it returns a value j such that Every element of A [p .. j ] is less than or equal to every element of A 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 jExplanation / Answer
a)At the end of the loop, the variables have the following values:x=13,j=9,i=10
The indices will not walk of the array. At the first check i<j, i=p and jp (because A[p]=x). If i=j, the algorithm will terminate without accessing "invalid" elements. If i<j, the next loop will also have indices i and j within the array, (because ir and jp). Note that if one of the indices gets to the end of the array, then i won't be less or equal to j any more.
As for the return value, it will be at least one less than j. At the first iteration, either (1) A[p] is the maximum element and then i=p and j=p<r or (2) it is not and A[p] gets swapped with A[j] where jr. The loop will not terminate and on the next iteration, j gets decremented (before eventually getting returned). Combining those two cases we get pj<r
B ) Finally, it's easy to observe the following invariant:
Before the condition comparing i to j, all elements A[p..i1]x and all elements A[j+1..r]x
C) Initialization. The two repeat blocks establish just this condition.
Maintenance. By exchanging A[i] and A[j] we make the A[p..i]x and A[j..r]x. Incrementing i and decrementing j maintain this invariant.
Termination. The loop terminates when ij. The invariant still holds at termination.
The third bit follows directly from this invariant.
D) After the first iteration, p=ijr. If the process does not terminate, the index j must decrease such that j<r holds. So at the beginning of kth iteration, we have p=ijr and A[p..i] x,A[j..r] x. The index j can not run over p because of , A[p..i] x on the other hand, the index i can not run over r either because of A[j..r] x
E) Algorithm for Quick Sort Procedure to use Hoare - Partition
#include <stdbool.h>
int hoare_partition(int A[], int p, int r) {
int x = A[p],
i = p - 1,
j = r,
tmp;
while(true) {
do { j--; } while (!(A[j] <= x));
do { i++; } while (!(A[i] >= x));
if (i < j) {
tmp = A[i]; A[i] = A[j]; A[j] = tmp;
} else {
return j;
}
}
}
void quicksort(int A[], int p, int r) {
if (p < r - 1) {
int q = hoare_partition(A, p, r);
quicksort(A, p, q + 1);
quicksort(A, q + 1, r);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.