Problem $7-2($page $186)$ on quicksort with equal element values$\mathrm{.}7-2$ Quicksort with equal element values

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[p.q-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[p..q-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.

Do parts $($a$)$ and $($b$)$ from the textbook. Do not do $($c$)$ or $($d$).$ Instead:

$(c^{\text{'}})$ Show the steps of your Partition' algorithm on the input array $1,6,5,8,5,4,5$ with $p=1$ and

$r=7.$ That is$,$ partition the entire array. $($Similar to Figure $7\mathrm{.}1$ on page $172.)$

$(d^{\text{'}})$ State the loop invariant for your Partition' algorithm. You are not required to write the proof

of correctness, but the loop invariant you state must be correct and it must be strong enough to

prove the correctness of your algorithm.

Your Partition' procedure must not be randomized; it should use the final element of the array range

as the pivot, like Partition does. It should make a single pass over the array range. I recommend using

a while loop instead of a for loop, but it can be solved either way.