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. If all elements are equal, then when $\text{PARTITION}$ returns, $q = r$ and all elements in $A[p..q - 1]$ are equal. We get the recurrence $T(n) = T(n - 1) + T(0) + \Theta(n)$ for the running time, and so $T(n) = \Theta(n^2)$.

b. The $\text{PARTITION}'$ procedure:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
PARTITION'(A, p, r)
    x = A[p]
    i = h = p
    for j = p + 1 to r
        // Invariant: A[p..i - 1] < x, A[i..h] = x, A[h + 1..j - 1] > x, A[j..r] unknown.
        if A[j] < x
            y = A[j]
            A[j] = A[h + 1]
            A[h + 1] = A[i]
            A[i] = y
            i = i + 1
            h = h + 1
        else if A[j] == x
            exchange A[h + 1] with A[j]
            h = h + 1
    return (i, h)

c. $\text{RANDOMIZED-PARTITION}'$ is the same as $\text{RANDOMIZED-PARTITION}$, but with the call to $\text{PARTITION}$ replaced by a call to $\text{PARTITION}'$.

1
2
3
4
5
QUICKSORT'(A, p, r)
    if q < r
        (q, t) = RANDOMIZED-PARTITION'(A, q, r)
        QUICKSORT'(A, p, q - 1)
        QUICKSORT'(A, t + 1, r)

d. Putting elements equal to the pivot in the same partition as the pivot can only help us, because we do not recurse on elements equal to the pivot. Thus, the subproblem sizes with $\text{QUICKSORT}'$, even with equal elements, are no larger than the subproblem sizes with $\text{QUICKSORT}$ when all elements are distinct.