Like mergeSort, quickSort is a sorting algorithm based on the divide-and-conquer
ID: 3769392 • Letter: L
Question
Like mergeSort, quickSort is a sorting algorithm based on the divide-and-conquer paradigm. As we have seen, the worst case running time of mergeSort is (n log n), as was shown by solving the mergeSort recurrence relation. The situation with the running time of quickSort is a bit murkier, and more interesting. Here is Python code for quickSort that I wrote a few years ago:
def partition(L, first, last):
# Pick L[first] as the "pivot" around which we partition the list
p = first
for current in range(p+1, last+1):
if L[current] < L[p]:
swap(L, current, p+1)
swap(L, p, p+1)
p = p + 1
return p
def generalQuickSort(L, first, last):
# Base case: if first == last, there is nothing to do
# Recursive case: 2 or more elements in the slice L[first..last]
if first < last:
# Divide step
p = partition(L, first, last)
# Conquer step
generalQuickSort(L, first, p-1)
generalQuickSort(L, p+1, last)
# Combine step: there is nothing left to do!
Suppose that L is an already-sorted list (in increasing order) of length n. This problem asks you to figure out the worst case running time of the function call generalQuickSort(L, 0, n 1). Start by writing a recurrence relation and then solve it.
Hint: The complication with quickSort is that the choice of the “pivot” in the partition function affects the sizes of the two subproblems that are solved by the recursive calls. This in turn affects the overall running time quite significantly.
Explanation / Answer
When the pivot element is a unique minimum or maximum element the worst case for the generalQuicksort occurs.
Assume recursive calls:
|L|=0, |P|=n-1
|L|=1, |P|=n-2
|L|=2, |P|=n-3 ......|L|=n-1, |P|=0
The probability of recurrences of n possible ways is 1/n.
The recurrence relation running time is proportional to the sum as follows: n+(n-1)+(n-2)+...+2+1.
Therefore, the worst case running time of the function call generalQuickSort(L, 0, n 1)=O(n2 ).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.