$7\mathrm{.}4-2$

Show that quicksort's best$-$case running time is $(nlgn).$

The analysis of the expected running time of randomized quicksort in Section $7\mathrm{.}4\mathrm{.}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 quick$-$

sort's running time in this case?

b$.$ The Partition procedure returns an index $q$ such that each element of

$A[pdotsq-1]$ is less than or equal to $A[q]$ and each element of $A[q+1$dotsr$]$

is greater than $A[q].$ Modify the Partition procedure to produce a procedure

Partition ${?}^{\text{'}}(A,p,r),$ which permutes the elements of $A[pdotsr]$ and returns two

indices $q$ and $t,$ where $pqtr,$ such that

all elements of $A[qdotst]$ are equal,

each element of $A[pdotsq-1]$ is less than $A[q],$ and

each element of $A[t+1$dotsr$]$ is greater than $A[q].$

Like PARTITION, your PARTITION' procedure should take $(r-p)$ time.

c$.$ Modify the RANDOMIZED$-$QUICKSORT procedure to call Partition', and

name the new procedure RANDOMIZED$-$QUICKSORT ${?}^{\text{'}}.$ Then modify the

QUICKSORT procedure to produce a procedure $QUICKSOR{T}^{\text{'}}(p,r)$ that calls

RANDOMIZED$-$PARTITION ${?}^{\text{'}}$ 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\mathrm{.}4\mathrm{.}2$ to

avoid the assumption that all elements are distinct?