CS 112: Data Structures
Sesh Venugopal
Quicksort Algorithm
Divide and Conquer
Mergesort and Quicksort both use what’s called a “divide and conquer” technique
In Mergesort, the “divide” step is trivial – just divide the array in two halves. All the work is done in “combine”, where sorted subarrays are merged
Sesh Venugopal CS 112: Quicksort 2
Divide and Conquer in Quicksort
In Quicksort, the divide and conquer process works in exactly the opposite way. As in, all the work is done in the “divide” step, and nothing at all is done in the ”combine” step.
01234567
Typically, the first item in the (sub)array is picked as the pivot
SPLIT
01234567
[<15 ][>=15]
15
12
13
11
20
15
22
14
13 12 14 11
15
20
15
22
Sort recursively
After the split, the pivot is in its correct sorted place
Sort recursively
Sesh Venugopal
CS 112: Quicksort
3
Split
Pivot is the first value, 15
Start with L at the next index after the pivot, and R at the last index
Iteration 1
If A[L] < pivot, then advance L to next index, otherwise stop – here L advances all the way to 20, where it stops because 20 is not < than 15
If A[R] >= pivot, then advance R to previous index, otherwise stop – here R does not advance at all since 14 is not >= 15
Swap the values at L and R, then advance L up by 1 and R down by 1, to prepare for next iteration
01234567
LR
01234567
✓✓✓✗
L R
01234567
✓✓✓✗ ✗ LR
01234567
LR
15
12
13
11
20
15
22
14
15
12
13
11
20
15
22
14
15
12
13
11
20
15
22
14
15
12
13
11
14
15
22
20
Sesh Venugopal
CS 112: Quicksort
4
Iteration 2
If A[L] < pivot, then advance L to next index, otherwise stop – here L does not advance at all since 15 is not < 15
If A[R] >= pivot, then advance R to previous index, otherwise stop – here R advances to 15
Normally it would have also compared 15, but because it has already been compared via L, R stops without comparing 15 against the pivot.
So the condition to advance R is modified to this:
If R > L and A[R] >= pivot, then R–
At this point, both L and R have finished moving as far as they could,
because R is not > L
So we need wrap up. This is done by swapping A[L-1] with the pivot:
0 1
2 3
4 5 6 7
15
12
13
11
14
15
22
20
✗
L
R
01234567
✗✓ LR
01234567
15
12
13
11
14
15
22
20
14
12
13
11
15
15
22
20
Sesh Venugopal
CS 112: Quicksort
5
< 15
>= 15
SplitPoint
Split Example 2
Pivot is 9
Iteration 1
left starts at item 3, right starts at item 12
left moves up to 14 and stops (14 not < 9),
right moves down to 5 and stops (5 not >= 9) swap 14 with 5, then left++, right–
Iteration 2
left starts at item 7, right starts at item 7
left moves past 7, but stops at 14 without comparing 14 because left has moved past right
So the condition to advance L is modified to this:
If L <= R and A[L] < pivot, then L++
left and right have crossed over, so right does not move at all (remember right only moves if right > left)
All items have been compared against pivot (right is not > left)
Swap A[left-1] (7) with pivot (9)
CS 112: Quicksort
✓✗✗✓✓
✓
Sesh Venugopal
6
Split: Extreme Case 1 (All items < pivot)
Condition to advance L:
If L <= R && A[L] < pivot, then L++
Pivot is 15
Iteration 1
L starts at item 12, R starts at item 14
L moves all the way through the array and stops when it moves past R (and goes out of bound)
R does not move at all, since R is not > L
All items have been compared against pivot (R is not > L)
Swap A[L-1] (14) with pivot (15)
Condition to advance R:
If R > L && A[R] >= pivot, then R–
01234567
LR
01234567
✓✓✓
01234567
SplitPoint
15
12
13
11
7
8
5
14
15
12
13
11
7
8
5
14
✓✓✓✓
RL
14
12
13
11
7
8
5
15
Sesh Venugopal
CS 112: Quicksort
7
Split: Extreme Case 2 (All items >= pivot)
Condition to advance L:
If L <= R && A[L] < pivot, then L++
Pivot is 3
Iteration 1
L starts at item12, R starts at item 14
L does not move at all (since 12 not < 3)
R moves all the way across. Past 13, it goes to item 12, but stops (without making a comparison) because R not > L
All items have been compared against pivot
(R is not > L)
Swap A[L-1] (3) with pivot (3), i.e. swap pivot with itself
Condition to advance R:
If R > L && A[R] >= pivot, then R–
01234567
LR
01234567
✓✓✓
LR
01234567
SplitPoint
3
12
13
11
7
8
3
14
3
12
13
11
7
8
3
14
✓✓✓✓
3
12
13
11
7
8
3
14
Sesh Venugopal CS 112: Quicksort 8
Algorithm split(A, lo, hi)
pivot ß A[lo]
left ß lo+1, right ß hi while (true) do
while (left <= right) do
if (A[left] < pivot) then
left++ else
break endif
endwhile
while (right > left) do
if (A[right] < pivot) then
break; else
right--
endif
endwhile
if (left >= right) then
break
endif
swap(A[left],A[right])
left++
right—
endwhile
swap(A[left-1],A[lo])
return left-1
Sesh Venugopal
CS 112: Quicksort 9
Recursion Tree Example 1
CS 112: Quicksort
01234567
split #c = 7 01234567
15
12
13
11
20
18
22
14
14
12
13
11
15
18
22
20
#c = 2
#c = 3
split
split
0123 567
split split
012 67
split #c = 1 12
#c = 1
18
22
20
11
12
13
14
#c = 2
20
22
11
12
13
12
13
Sesh Venugopal
10
Recursion Tree Example 2
01234567
split
01234567
4
1
3
2
7
6
5
8
#c = 7
2
1
3
4
7
6
5
8
#c = 2
split
split #c = 3 012 4567
split
45
5
6
7
1
2
3
#c = 1
5
6
Sesh Venugopal
CS 112: Quicksort 11
8
Recursion Tree Example 3
01234567
split #c = 7 01234567
split #c = 6 1234567
split #c = 5 234567
split
67
CS 112: Quicksort
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
3
4
5
6
7
8
#c = 1
7
8
Sesh Venugopal
12
Quicksort Running Time
Sesh Venugopal CS 112: Quicksort 13
Worst case
Sorted Input
01234567 01234567
1234567
5
234567
567
67
CS 112: Quicksort
Reverse Sorted Input
01234567 01234567
6 5
4 3
2 1
7
8
7
6
5
4
3
2
1
1
2
3
4
5
6
7
8
7
1
7
6
5
4
3
2
8
1
2
3
4
5
6
7
8
0123456
123456
6
1
7
6
5
4
3
2
2
3
4
5
6
7
8
2
6
5
4
3
7
3
4
5
6
7
8
12345
2345
Total number
of comparisons = (n-1)+(n-2)+…2+1 = n(n-1)/2 =
O(n2)
2
6
5
4
3
3
5
4
6
6
7
8
1
234
23
3
5
4
7
8
Sesh Venugopal
14
4
5
Best case
16
8
8
4
4
4
4
2
2
2
2
2
2
2
2
(n = 16, the number of comparisons are overcounted somewhat, for ease of analysis but the big O will be unchanged)
Total number of comparisons = 16 + 16 + 16 + 16 =
= 16*4 (height)
= 16*log2(16)
Which generalizes to
O(nlogn)
Sesh Venugopal CS 112: Quicksort 15
So why is Quicksort popular?
Insertion Sort Quicksort
Worst Case
O(n2)
O(n2)
Best Case
O(n)
O(nlogn)
Average Case
O(n2)
O(nlogn)
Sesh Venugopal
CS 112: Quicksort
16