Quick sort

PARTITION (A, p, r) 1. x = A[r] 2. i = p-1 3. for j = p to r - 1 4. if A[j] b. The PARTITION procedure returns an index q such that each element of A[p..q- 1] is less than or equal to A[g] and each element of A[q + 1..r] is greater than A[q]. Modify the PARTITION procedure to produce a procedure PARTITION' (A, p.r), which permutes the elements of A[p.r) and returns two indices q and t, where p q si sr, such that all elements of A[q..t] are equal, each element of A[p..9-1is less than A[q], and each element of A[t + 1..r] is greater than A[g]. Like PARTITION, your PARTITION' procedure should take @fr - p) time