Quicksort Let’s say that a pivot provides x, n-x separation (one partition has x
ID: 3668834 • Letter: Q
Question
Quicksort
Let’s say that a pivot provides x, n-x separation (one partition has x elements and the other partition has n-x) if x elements in an array are smaller than the pivot, and n x elements are larger than the pivot. Suppose Anthony can find a good pivot with n/3, 2n/3 separation in constant time. Suppose another student Lamar knows a technique which provides n/4, 3n/4 separation and works in constant time. Anthony and Lamar applied their secret techniques as a subroutine in QuickSort algorithm. Whose algorithm works asymptotically faster? Prove your statement.
Explanation / Answer
In quicksort the main thing that determines the time complexity is the choosing of the pivot element. The desirable case is to divide the list into two equal halves and the undesirabled case is that we get huge difference between the left and right halves. for example, in the cases like sorted ordered list in ascending or descending or an already sorted list or list having all the same values, the division of the lists becomes unequal sized lists .
before doing the quick sort we need to know the partition algorithm.
In the algorithm we select a pivot and after a single pass the positions of the elements would be
so selecting the pivot determines the sizes of the lists on which we perform the partition algorithm again.
So generally this selection of pivot is taken in different ways.
1) selecting first,last,or middle elements.
2) a more effective way is to take the median of the first,last,middle elements.
The beauty of the quick sort is that instead of the limitation cases however you take the pivot the time complexity would always be equal to 0(nlogn).
There are logN partitions, and to obtain each partitions we do N comparisons
(and not more than N/2 swaps). Hence the complexity is O(NlogN).
CASE 1:For example take a case of dividing n/10 and 9n/10.
n ------------------------- O(n)
/
n/10 9n/10 --------------------------- O(n)
/ /
n/100 9n/100 9n/100 81/100 ---------------------------- O(n)
Here levels size is decreasing because some branches are ending.
O(n log n) ---> even split is 1:9 even then O(n log n )
CASE 2: Consider an alternating split case
example: 1st level equal split
100
/
50 50
2nd level worst split
/ /
2 48 2 48
3rd Level equal split
/ / / /
1 1 24 24 1 1 24 24
even in this worst case the complexity is O(n log n).
Therefore,Anthony and lamar's techniques have the complexity of O(n logn) asymptotically.
elements < pivot pivot element elements > pivotRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.