Consider that duplicate elements may occur in a list to be sorted by QUICK SORT.

(a) Modify the pseudo code of function PARTITION so that all elements the same as the pivot will not be considered in subsequent rounds of recursive calls.

(b) Argue that the worst case running time of the modified QUICK SORT is O(kn) if there are only k distinct elements in the input list.

(c) Which of the following upper bounds is best for the average case time complexity of the modified QUICK SORT algorithm?

(i) O(n log2 n)

(ii) O(k log2 n)

(iii) O(n log2 k)

(iv) O(k log2 k)

2. then q=PARTITION(A, p,r) QUICKSORT (A, p, q -1) QUICKSORT (A, q +1,r) 4 PARTITION (A, p, r) 1 x A[r] 3 for j p tor-1 4 do if ALj] sx then i i I exchange Ali] A[j] 7 exchange A[i+1]A[r] 8 return i 1 2. then q=PARTITION(A, p,r) QUICKSORT (A, p, q -1) QUICKSORT (A, q +1,r) 4 PARTITION (A, p, r) 1 x A[r] 3 for j p tor-1 4 do if ALj] sx then i i I exchange Ali] A[j] 7 exchange A[i+1]A[r] 8 return i 1