CS 112: Data Structures
Sesh Venugopal
Quicksort Algorithm – Fine Tuning
Fine Tuning Running Time
Since quicksort can sort an array in place (without using extra array space, unlike mergesort, which needs extra storage), and the average running time is O(nlogn),it is widely used in practice
A core set of fine-tuning techniques have been developed to make quicksort run even better in real time
IMPORTANT: These techniques do not change the big O running times!
Sesh Venugopal CS 112: Quicksort Fine Tuning 2
Fine Tuning Technique #1
Defend against worst case time for sorted input
A good sorting algorithm should do minimal work if the input is already in sorted order
But quicksort’s behavior is the worst for sorted inputs, O(n2) running time
CS 112: Quicksort Fine Tuning
This first fine-tuning technique works to correct this aberration, by picking the median of the first, middle, and last items as the pivot (instead of always picking the first):
[2, 5, 3, 15, 23, 25, 81, 16, 10] median(2,23,10) = 10
Swap first with median
[10, 5, 3, 15, 23, 25, 81, 16, 2] Then call split
[8, 5, 3, 15, 1, 7, 25, 81, 16, 10] median(8,1,10) = 8
No need to swap with first, since 8 is first
[8, 5, 3, 15, 1, 7, 25, 81, 16, 10] Then call split
Alternatively, median(8,7,10)=8
(since there is an even number of items)
Sesh Venugopal
3
Since median is brought to the first position, the split algorithm doesn’t change – it still works with the first item as the pivot
Sorted Input, no fine tuning
01234567 01234567
1234567
5
234567
Sorted Input, pivot is median
01234567
med(1,4,8)
01234567
med(1,2,3) med(5,6,8)
1
2
3
4
5
7
6
7
8
1
2
3
4
5
6
7
8
7
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
6
2
3
012 4567
67
If array length = 2, first item defaults to pivot
2
3
4
5
6
7
8
1
2
3
5
6
7
8
1
3
4
5
6
7
8
7
8
Total #c=13
Total #c=28
567
67
6
7
8
1
7
8
Sesh Venugopal
CS 112: Quicksort Fine Tuning
4
Fine Tuning Technique #2
Defend against recursion overhead
The recursive nature of quicksort results in running time overhead due to recursive method calls
This is not a big issue when the subarrays being sorted recursively are large enough, since the added overhead of a recursive call can be overlooked relative to the computational time to sort large arrays
Trouble happens when the subarray being sorted gets to be too small to afford recursive calls
CS 112: Quicksort Fine Tuning
When a subarray gets sufficiently small, quicksort is NOT used to sort it. Instead, insertion sort is used
Sesh Venugopal
5
Yes, the average case of insertion sort is O(n2) compared to quicksort’s O(nlogn), but at small array sizes, the asymptotic big O times no longer apply – insertion sort will be comparable or even faster than quicksort
Fine Tuning Technique #2
When subarray gets too small, switch to insertion sort
CS 112: Quicksort Fine Tuning
Ins Sort
Ins Sort
Ins Sort
Insertion Sort
Insertion Sort
Insertion Sort
Exactly what ”too small” is depends on the machine. Around 50-75 is a good starting number, which can be tweaked with some experimenting
Sesh Venugopal 6
Fine Tuning Technique #3
Defend against excessive recursion stack space usage
Every time a recursive call is made, the execution engine needs to push the calling method’s state info on the activation stack
Activation stack info includes the address of the statement to which the recursive call must return, and the values of the local variables at the time of the call
Là Rà
O(1) O(1)
before second recursive call
before first recursive call
. . .
R, A, left, right, splitPoint
R, A, left, right, splitPoint
Activation stack
L,R: memory address of respective statements A: memory address of array
left, right, splitPoint: values of local variables
O(1) space for all of these
Sesh Venugopal
CS 112: Quicksort Fine Tuning 7
Recursion Stack Space Usage: Worst Case
L L
L L
For eventual return to right recursion
For eventual return to right recursion
R,A,… O(1)
n-1
R,A,…
R,A,…
R,A,…
n-2
2
For eventual return to right recursion
O(1)
O(1) O(1)
n-1 items on stack, total space used is O(n)
1
Sesh Venugopal
CS 112: Quicksort Fine Tuning
8
n
Recursion Stack Space Usage: Best Case
We could choose to do the right recursion first! (The left and right recursion calls are independent, so they can be done in either order.)
splitPoint ß split(A,left,right) R àquicksort(A,splitPoint+1,right)
L àquicksort(A,left,splitPoint-1)
R
R
R R
Stacked, but popped right after, because the right recursion has no depth
L,A,…
L,A,…
O(1) O(1)
O(1) O(1) 9
n
n-1
Ditto
n-2
2
L,A,…
L,A,…
So the stack never uses more than O(1) space
1
Sesh Venugopal
CS 112: Quicksort Fine Tuning
Recursion Stack Space Usage: General Case
So what should we do in the general case to minimize stack space usage?
Answer: Always recurse on the smaller side first!
splitPoint ß split(A,left,right)
if ((splitPoint – left) < (right – splitPoint) then quicksort(A,left,splitPoint-1) quicksort(A,splitPoint+1,right)
else quicksort(A,splitPoint+1,right) quicksort(A,left,splitPoint-1)
endif
Sesh Venugopal
CS 112: Quicksort Fine Tuning 10
Recursion Stack Space Usage: General Case
For an array of size n, the smaller side’s size can be at most (worst case) n/2-1 (let’s assume n/2 for sake of analysis)
If we recurse on the smaller side first, in the next round the smaller side would be n/4, then n/8 ....
And each time we recurse, the address to which we return for the other side recursion is stacked (either for left side or right side, whichever is bigger)
We would hit bottom in log n steps, and log n would be the height of the stack – no path in the recursion tree can be more than log n deep
R/L,A,...
R/L,A,...
R/L,A,...
R/L,A,...
Sesh Venugopal CS 112: Quicksort Fine Tuning
11
n
n/2
n/4
1
So the stack never uses more than O(log n) space