Computational Complexity - Bachelor's and Master's Theses
Nima Zeini Jahromi: Smoothed Analysis of Quicksort with Median-Of-Three Pivot Rule
Bachelor's Thesis, 2008.
Advisor: Dr. Bodo Manthey
Sorting in general and in particular the Quicksort algorithm are fundamental to many applications and have been subject to extensive theoretical investigation. Unfortunately, the two classical modes of algorithm analysis, worst-case and average-case, often prove insufficient to explain practical results, the former being far too pessimistic while the results of the latter lack significance for instances occurring in the real world.
Consequently, the most widespread Quicksort algorithm does not use the worst-case optimal median find method, but a far simpler technique: The median among the first, middle and last element of the list becomes the pivot (instead of the median of the whole list). The list is then split into elements smaller and larger than the pivot, and these two sublists sorted recursively. This is called Median-of Three Pivoting and through inclusion in the C++ standard library's Quicksort implementation finds employment in millions of programs. Therefore, a theoretical runtime analysis seems sensible.
To counter the problems of worst-case and average-case estimations, Spielman and Teng have introduced the notion of Smoothed Analysis in order to find an explanation for the behaviour of the simplex algorithm which has exponential worst-case running time but in practice works extraordinarily well. Smoothed analysis tries to serve an alternative in between worst-case and average case. It analyzes an instance given from an evil adversary which is subject to slight perturbation. Qualities like running time or approximability then depend on input size and perturbation amount. The precise model of these perturbation is of high importance: There are many parameters which can be randomly altered, some of which can destroy the whole structure of the instance with only minor change and render it simple to solve, without this happening in practice. Unfortunately, there exists no standard model of smoothed analysis until today, leaving the parameters to be chosen appropriately to the individual case. Nevertheless, smoothed analysis is being successfully applied.
In 2007, Manthey and Tantau performed a smoothed analysis of the standard Quicksort algorithm which uses the first element of the list as pivot, under uniformly distributed additive noise from range [0, d]. They proved the smoothed number of Left-to-Right Maxima in suchlike perturbed sequences to be Θ(√(n/d) + log n) and the same estimation to hold for the height of the binary search tree built during the sorting process. They found the smoothed number of Quicksort comparisons to be &Theta(n/(d+1)*√(n/d) + n log n). Note that the analyzed sequences had values in the range [0, 1], reflected by the fact that for d ≤ 1/n, the search tree height becomes linear and the smoothed number of Quicksort comparisons equals the worst-case of Θ(n2), and for d ≥ (n/log2n)1/3 the number of comparisons lies in Θ(n log n). For d ∈ Θ(n/log2n), the height of the search tree becomes logarithmic.
In the following we apply the approach of Manthey and Tantau to Quicksort with median-of-three pivoting, yielding a smoothed lower bound of Θ(√(n/d) + log n) on the number of left-to-right maxima and consequently also on the search tree height. We derive a lower bound on the number of comparisons of Θ(n √(n/d) + nlog n) for d ∈ o(1). We presume Quicksort with median-of-three pivoting to make asymptotically at most as many comparisons as standard Quicksort, which implies that the median-of three pivoting poses no improvement over the standard pivoting in a smoothed analysis under additive noise. We conclude with suggestions of how to modify the pivoting in order to reduce the smoothed complexity of Quicksort. It remains to be found whether a different perturbation model better explains the advantage of median-of-three pivoting in practice, for which already some suggestions have been made.
Smoothed Analysis of Quicksort and Hoare's Find.
arXiv:0904:3898 [cs.DS], 2009.
On Smoothed Analysis of Quicksort and Hoare's Find.
International Computing and Combinatorics Conference (COCOON) in Lecture Notes in Computer Science 5609:158-167. Springer, 2009.