In this question we wish to develop a variant of the PARTITION procedure which works as follows. PARTITION here is to choose the last element as pivot, permute the input array A[p, . . . , r] and return two indices q and t such that: q is the final index of the pivot, and p q t r All elements of A[p, . . . , q] are equal A[q + 1, . . . , t] < A[q] A[t + 1, . . . , r] > A[q]

(a) (10%) Develop the PARTITION pseudo-code associated with the above strategy. Your PARTITION procedure should run in (n) time, where n is the length of the input array. No credit will be given otherwise. (b) (10%) Develop the corresponding QUICKSORT that is associated with this PARTITION function.

(c) (10%) Is the resulting QUICKSORT stable? Prove your answer or else provide a counter-example.