Consider modifying the \(\textsc{Partition}\) procedure by randomly picking three elements from array \(A\) and partitioning about their median (the middle value of the three elements). Approximate the probability of getting at worst an \(\alpha\)-to-\((1-\alpha)\) split, as a function of \(\alpha\) in the range \(0 < \alpha < 1\).
The median-of-3 method improves the likelihood of choosing a good pivot by selecting the middle value among three random elements. Let’s calculate the probability of achieving a reasonably balanced partition.
Consider the \(n\) elements in their sorted order as positions \(1, 2, \ldots, n\). A pivot at position \(i\) creates subarrays of sizes \(i-1\) and \(n-i\).
A split is “at worst \(\alpha\)-to-\((1-\alpha)\)” (i.e., at least this balanced) when the pivot falls in the middle \(1-2\alpha\) fraction of elements. Specifically, the pivot position \(i\) must satisfy:
\[\alpha n \leq i \leq (1-\alpha)n\]This gives us the “good” region of size approximately \((1-2\alpha)n\).
With standard randomized quicksort (one random pivot), the probability of a good split is:
\[P_1 = 1 - 2\alpha\]Now we randomly select three elements with positions \(i_1, i_2, i_3\). The median becomes the pivot. For the median to fall in the good region \([\alpha n, (1-\alpha)n]\), we need:
At least 2 of the 3 elements must be in the good region.
If all 3 are in the good region, the median is definitely good. If only 1 is in the good region, the median is one of the two bad elements. If exactly 2 are good, the median is one of the good ones.
Let \(p = 1 - 2\alpha\) be the probability that a single random element falls in the good region.
The probability that the median of 3 random elements is good is:
\[\begin{align*} P_3 &= P(\text{all 3 good}) + P(\text{exactly 2 good}) \\ &= p^3 + \binom{3}{2}p^2(1-p) \\ &= p^3 + 3p^2(1-p) \\ &= p^3 + 3p^2 - 3p^3 \\ &= 3p^2 - 2p^3 \\ &= p^2(3 - 2p) \end{align*}\]Substituting \(p = 1 - 2\alpha\):
\[P_3 = (1-2\alpha)^2(3 - 2(1-2\alpha)) = (1-2\alpha)^2(1 + 4\alpha)\]Expanding:
\[\begin{align*} P_3 &= (1 - 4\alpha + 4\alpha^2)(1 + 4\alpha) \\ &= 1 + 4\alpha - 4\alpha - 16\alpha^2 + 4\alpha^2 + 16\alpha^3 \\ &= 1 - 12\alpha^2 + 16\alpha^3 \end{align*}\]For \(\alpha = 0.1\) (requiring a 9-to-1 split or better):
- Single pivot: \(P_1 = 1 - 2(0.1) = 0.8\)
- Median-of-3: \(P_3 = 1 - 12(0.01) + 16(0.001) = 1 - 0.12 + 0.016 = 0.896\)
For \(\alpha = 0.25\) (requiring a 3-to-1 split or better):
- Single pivot: \(P_1 = 1 - 2(0.25) = 0.5\)
- Median-of-3: \(P_3 = 1 - 12(0.0625) + 16(0.015625) = 1 - 0.75 + 0.25 = 0.5\)
So the benefit diminishes as \(\alpha\) increases.
Final answer: The probability of getting at worst an \(\alpha\)-to-\((1-\alpha)\) split with median-of-3 partitioning is approximately:
\[P_3 = (1-2\alpha)^2(1+4\alpha) = 1 - 12\alpha^2 + 16\alpha^3\]