7-2

Quicksort with equal element values
The analysis of the expected running time of randomized quicksort in Section 7.4.2 assumes that all element values are distinct. In this problem, we examine what happens when they are not.
a. Suppose that all element values are equal. What would be randomized quicksort’s running time in this case?
b. The PARTITION procedure returns an index q such that each element of A[p..q-1] is less than or equal to A[q] 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 t r, such that
all elements of A[q..t] are equal,
each element of A[p..q -1] is less than A[q] , and
each element of A[t+1..r] is greater than A[q] .
Like PARTITION, your PARTITION' procedure should take $\theta(r-p)$ time.
c. Modify the RANDOMIZED-QUICKSORT procedure to call PARTITION', and name the new procedure RANDOMIZED-QUICKSORT'. Then modify the QUICKSORT procedure to produce a procedure QUICKSORT'(p, r) that calls RANDOMIZED-PARTITION' and recurses only on partitions of elements not known to be equal to each other.
d. Using QUICKSORT', how would you adjust the analysis in Section 7.4.2 to avoid the assumption that all elements are distinct?
a. The running will be $\theta(n^2)$.Similar to quick sort because RANDOM will get a same pivot element as A[r] since all the elements are similar and this would provide unbalanced split of n-1 and 0 elements. The running time for n-1 and 0 elements is $\theta(n^2)$
b. PARTITION'(A,p,r,q,t)
i = p-1
j = p
x = A[r]
k = p-1
for j = p to r-1
  if A[j] $\leq$ x
  i = i+1
   if A[i] = x
   k = k-1
  swap A[i] and A[j]
   if A[j] == x
   k = k+1
   swap A[k+i] and A[j]
Exchange A[k+1+i] and A[q]
q = i+1
t = k+1+i
c. QUICKSORT(A,p,r)
if p < r
RADOMIZED-QUICKSORT(A,p,r,q,t)
QUICKSORT(A,p,q-1)
QUICKSORT(A,t+1,r)
RADOMIZED-QUICKSORT(A,p,r)
i = Random(p,r)
swap A[i] and A[r]
PARTITION'(A,p,r)
d.Needs more research.