(1) (a) We saw in class a proof that the worst case performance for QuickSort in
ID: 3766218 • Letter: #
Question
(1) (a) We saw in class a proof that the worst case performance for QuickSort in terms of the number of comparisons is O(N2) for a list of size N. Explain the circumstances under which the worst case arises. (b) The worst case is substantially worse than the average case for QuickSort - the average case is O(N log2 N). For a list of size 10 million and assuming that each comparison takes one microsecond, compare the time required for the average case with that required for the worst case. (c) Based on your answer to part (a), consider how likely it is that the worst case will arise? Develop an argument to explain how likely it is that the worst case will arise. (d) The key idea in assessing worst case conditions involves counting the number of times a worst case partitioning arises. What is a worst case partitioning? For a list of size N, how many worst case partitioning scenarios are there? Experimentally count the number of times that a worst case partitioning arises vs. the number of times that a non-worst case partitioning arises. As well experimentally determine the average number of comparisons performed by QuickSort.
Explanation / Answer
A. Worst case can occur in following scenerios :
If the first element is always chosen as the pivot, then an already sorted list is the worst-case. Often there's a high probability that the array is already/nearly sorted, so this implementation is rather poor.
Analogously, selecting the last element as the pivot is bad for the same reason.
Some implementations tries to avoid this problem by choosing the middle element as the pivot. This would not perform as badly on already/nearly sorted arrays, but one could still construct an input that would exploit this predictable pivot selection and make it run in quadratic time.
Thus, you get randomized pivot selection algorithms, but even this doesn't guarantee O(N log N).
So other algorithms were developed that would use some information from the sequence before picking a pivot. You can of course scan the whole sequence and find the median, and use that as the pivot. This guarantees O(N log N), but of course slower in practice.
So some corners are cut, and people devised the median-of-3 algorithm. Of course, later even this was exploitable by the so-called median-of-3 "killer".
So more attempts are made at coming up with more "intelligent" pivot selection algorithms that guarantees O(N log N) asymptotic behavior that is still fast enough to be practical, with varying degree of success.
So really, unless one specifies a particular implementation of Quicksort, the question of when the worst case scenario occurs is ill-defined. If you use the so-called median-of-medians pivot selection algorithm, there is no quadratic worst-case scenario.
Most library implementations, however, are likely to forfeit O(N log N) guarantee for much faster sorting in the average case.
B. For average case :
total comparisons = N log N // base 2
total comparison = (7*10000000)*log10
total time = (7*10000000)*log10 / 1000000
total time = 70 log 10 = nearly 4 sec
For worst case :
total comparison = N*N = 10000000 * 10000000
total time = 10000000 * 10000000 / 1000000
total time = 100000000 = nearly 1157 days
So, you can imagine the difference
C. I believe I've already answered this question in part A itself.
To summerize, in a nearly sorted array, worst case is very likely to come. It can be minimized but can not be guaranteed to avoid.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.