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.
- Suppose that all element values are equal. What would be randomized quicksort’s running time in this case?
- The \(\textsc{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 \(\textsc{Partition}\) procedure to produce a procedure \(\textsc{Partition}'(A, p, r)\), which permutes the elements of \(A[p..r]\) and returns two indices \(q\) and \(t\), where \(p \leq q \leq t \leq 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 \(\textsc{Partition}\), your \(\textsc{Partition}'\) procedure should take \(\Theta(r-p)\) time.
- Modify the \(\textsc{Randomized-Partition}\) procedure to call \(\textsc{Partition}'\), and name the new procedure \(\textsc{Randomized-Partition}'\). Then modify the \(\textsc{Quicksort}\) procedure to produce a procedure \(\textsc{Quicksort}'(A, p, r)\) that calls \(\textsc{Randomized-Partition}'\) and recurses only on partitions of elements not known to be equal to each other.
- Using \(\textsc{Quicksort}'\), how would you adjust the analysis in Section 7.4.2 to avoid the assumption that all elements are distinct?
Equal elements pose a significant challenge for standard quicksort. Three-way partitioning provides an elegant solution by grouping equal elements together.
A.
When all elements are equal, standard randomized quicksort degrades to its worst-case behavior: \(\Theta(n^2)\).
With all elements equal to some value \(v\), every element satisfies \(A[j] \leq pivot\) during partitioning. This causes \(\textsc{Partition}\) to return \(q = r\), creating maximally unbalanced splits: the left subarray has \(n-1\) elements (all equal to \(v\)), and the right subarray is empty.
The recursion follows the same pattern as sorting an already-sorted array:
\[T(n) = T(n-1) + T(0) + \Theta(n) = T(n-1) + \Theta(n) = \Theta(n^2)\]This is highly inefficient for a problem that requires no actual sorting.
B.
The key insight is to create three regions: elements less than the pivot, elements equal to the pivot, and elements greater than the pivot.
This procedure maintains three regions: \(A[p..k]\) contains elements \(< x\), \(A[k+1..i]\) contains elements \(= x\), and \(A[i+1..j-1]\) contains elements \(> x\). It runs in \(\Theta(r-p)\) time, performing at most \(2(r-p)\) swaps.
C.
Notice that elements in \(A[q..t]\) are all equal and already in their final positions, so we don’t recurse on this region. We only recurse on \(A[p..q-1]\) (elements less than the pivot) and \(A[t+1..r]\) (elements greater than the pivot).
D.
With three-way partitioning, the analysis from Section 7.4.2 requires only minor adjustments. Two elements \(z_i\) and \(z_j\) are compared only if one of them is chosen as a pivot before any element with a value strictly between \(z_i\) and \(z_j\). If \(z_i = z_j\), they’re never compared, since they end up together in the same equality group. So if we sort the elements by value and group them into the \(k\) distinct values, elements sharing a value never get compared to each other.
The expected number of comparisons becomes:
\[\mathbb{E}[X] = \sum_{i=1}^{k-1} \sum_{j=i+1}^{k} \frac{2 \cdot n_i \cdot n_j}{n_i + n_{i+1} + \cdots + n_j}\]where \(n_i\) is the number of elements with the \(i\)-th distinct value.
In the worst case (all distinct elements), this reduces to the original \(O(n \lg n)\). In the best case (all equal elements), we have \(k=1\), so \(\mathbb{E}[X] = 0\), and the running time is \(\Theta(n)\) (one pass through the array).
For any distribution of values, the expected running time is \(O(n \lg k)\), where \(k \leq n\) is the number of distinct values.