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 quick-sort's running time in this case?

b. The $\text{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 $\text{PARTITION}$ procedure to produce a procedure $\text{PARTITION}'(A, p, r)$ which permutes the elements of $A[p..r]$ and returns two indices $q$ and $t$ where $p \le q \le t \le 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 $\text{PARTITION}$, your $\text{PARTITION}'$ procedure should take $\Theta(r - p)$ time.

c. Modify the $\text{RANDOMIZED-QUICKSORT}$ procedure to call $\text{PARTITION}'$, and name the new procedure $\text{RANDOMIZED-QUICKSORT}'$. Then modify the $\text{QUICKSORT}$ procedure to produce a procedure $\text{QUICKSORT}'(p, r)$ that calls $\text{RANDOMIZED-PARTITION}'$ and recurses only on partitions of elements not know to be equal to each other.

d. Using $\text{QUICKSORT}'$, how would you adjust the analysis of section 7.4.2 to avoid the assumption that all elements are distinct?

a. Since all elements are equal, $\text{RANDOMIZED-QUICKSORT}$ always returns $q = r$. We have recurrence $T(n) = T(n - 1) + \Theta(n) = \Theta(n^2)$.

b.

PARTITION'(A, p, r)
    x = A[p]
    low = p
    high = p
    for j = p + 1 to r
        if A[j] < x
            y = A[j]
            A[j] = A[high + 1]
            A[high + 1] = A[low]
            A[low] = y
            low = low + 1
            high = high + 1
        else if A[j] == x
            exchange A[high + 1] with A[j]
            high = high + 1
    return (low, high)

c.

QUICKSORT'(A, p, r)
    if p < r
        (low, high) = RANDOMIZED-PARTITION'(A, p, r)
        QUICKSORT'(A, p, low - 1)
        QUICKSORT'(A, high + 1, r)

d. Since we don't recurse on elements equal to the pivot, the subproblem sizes with $\text{QUICKSORT}'$ are no larger than the subproblem sizes with $\text{QUICKSORT}$ when all elements are distinct.