Quicksort with equal element values. $(30$ points$)$ The analysis of the expected

running time of randomized Quicksort in class $($corresponding to Section $7\mathrm{.}4\mathrm{.}2$ in textbook$)$

assumes that all element values are distinct. In this problem, we examine what happens

when they are not, i$.$e$.,$ there exist same$-$valued elements in the array to be sorted.

The Quicksort algorithm relies on the following partition algorithm, which finds a pivot

randomly, and then put all the numbers less than or equal to the pivot in the left, and put

all the numbers greater than the pivot in the right, and then return the pivot location,

as well as the left and right sublists for recursive calls.

Algorithm $2$: Partition $(A,p,r)$

$q=$ RANDOM $(p,r)\frac{\text{;}}{\frac{?}{?}}$ generate a random number in the range of $p,r$

$L=$ empty list, $R=$ empty list;

for each element $a$ in A except $A[q]$ :

if $aA[q]$ :

append a to $L$;

else append a to $R$;

$A=$append$(L,A[q],R)$;

$8$ returen $A,$ q;

In this algorithm, the list to be sorted is $A,$ and we use $p$ and $r$ to denote the left$-$most and

right$-$most indices of the currently processing subarray, respectively. For example, in the

initial call of the Quicksort algorithm, we will let $p=0$ and $r=n-1,$ which correspond to

the whole original array. The PARTITION $(A,p,r)$ 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].$

$($a$)(10$ points$)$ Suppose there are $n$ elements and all element values are equal. What

would be randomized Quicksort's running time in this case?

$($b$)(10$ points$)$ Modify the PARTITION procedure to produce a procedure $PARTITIO{N}^{\text{'}}(A,p,r),$

which permutes the elements of $A[p$:$r]$ and returns two indices $q$ and $t,$ where

$pqtr,$ such that:

i$.$ all elements of $A[q$:$t]$ are equal,

ii$.$ each element of $A[p$:$q-1]$ is less than $A[q],$ and

iii. each element of $A[t+1$:$r]$ is greater than $A[q]$

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

$($c$)(10$ points$)$ Now you have a $PARTITIO{N}^{\text{'}}(A,p,r)$ algorithm, based on this algo$-$

rithm, provide the pseudocode of a QUICKSORT $(A)$ algorithm which calls PAR$-$

$TITIO{N}^{\text{'}}(A,p,r)$ as a subroutine, so that it recurses only on partitions of elements

not known to be equal to each other. $[$Hint: it will looks very similar to our Quick$-$

sort pseudocode in the lecture slides, you only need to make minor modifications to

recurse on the partitions produced by $PARTITIO{N}^{\text{'}}(A,p,r).]$