Today’s Musical Selections
Today’s great song is from Haerts.
Quicksort
Review: Merge Sort Runtime
Let’s consider an array of size 8:
-
Merge 1:
-
8 arrays of size 1 into 4 arrays of size 2
-
so 4 O(n) merges where n = 2
-
-
Merge 2:
-
4 arrays of size 2 into 2 arrays of size 4
-
so 2 O(n) merges where n = 4
-
-
Merge 3:
-
2 arrays of size 4 into 1 arrays of size 8
-
so 1 O(n) merges where n = 8
-
-
So given n = 8, we have done 3 O(n) steps, or O(n log n).
Review: Merge Sort Runtime
Step |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
8 |
|
5 |
|
7 |
|
3 |
|
4 |
|
11 |
|
6 |
|
-1 |
|
1 |
|
5 |
8 |
|
|
3 |
7 |
|
|
4 |
11 |
|
|
-1 |
6 |
|
2 |
|
|
3 |
5 |
7 |
8 |
|
|
|
|
-1 |
4 |
6 |
11 |
|
|
3 |
|
|
|
|
-1 |
3 |
4 |
5 |
6 |
7 |
8 |
11 |
|
|
|
|
Review: Merge Sort Runtime
| Measure | Best Case | Worst Case | Average Case |
|---|---|---|---|
Time |
O(n log n) |
O(n log n) |
O(n log n) |
Space |
O(n) |
O(n) |
O(n) |
(Our implementation used a lot of extra space, but you can get by with just one extra array of size n.)
Divide and Conquer
Divide and conquer is an algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.
Quicksort: Overview
8 |
5 |
7 |
3 |
4 |
11 |
6 |
-1 |
-
In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller
-
This continues until arrays of size 1 are reached, at which point the entire array is sorted
Quicksort: Overview
8 |
5 |
7 |
3 |
4 |
11 |
6 |
-1 |
-
In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller
-
This continues until arrays of size 1 are reached, at which point the entire array is sorted
Quicksort: Overview
5 |
7 |
3 |
4 |
6 |
-1 |
8 |
11 |
-
In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller
-
This continues until arrays of size 1 are reached, at which point the entire array is sorted
Quicksort: Overview
5 |
7 |
3 |
4 |
6 |
-1 |
8 |
11 |
5 |
7 |
3 |
4 |
6 |
-1 |
8 |
11 |
-
In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller
-
This continues until arrays of size 1 are reached, at which point the entire array is sorted
Quicksort: Overview
5 |
7 |
3 |
4 |
6 |
-1 |
8 |
11 |
3 |
4 |
-1 |
5 |
7 |
6 |
8 |
11 |
-
In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller
-
This continues until arrays of size 1 are reached, at which point the entire array is sorted
Quicksort: Overview
5 |
7 |
3 |
4 |
6 |
-1 |
8 |
11 |
3 |
4 |
-1 |
5 |
7 |
6 |
8 |
11 |
3 |
4 |
-1 |
5 |
7 |
6 |
8 |
11 |
-
In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller
-
This continues until arrays of size 1 are reached, at which point the entire array is sorted
Quicksort: Overview
5 |
7 |
3 |
4 |
6 |
-1 |
8 |
11 |
3 |
4 |
-1 |
5 |
7 |
6 |
8 |
11 |
-1 |
3 |
4 |
5 |
6 |
7 |
8 |
11 |
-
In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller
-
This continues until arrays of size 1 are reached, at which point the entire array is sorted
Quicksort: Overview
5 |
7 |
3 |
4 |
6 |
-1 |
8 |
11 |
3 |
4 |
-1 |
5 |
7 |
6 |
8 |
11 |
-1 |
3 |
4 |
5 |
6 |
7 |
8 |
11 |
-1 |
3 |
4 |
5 |
6 |
7 |
8 |
11 |
-
In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller
-
This continues until arrays of size 1 are reached, at which point the entire array is sorted
Quicksort: Overview
5 |
7 |
3 |
4 |
6 |
-1 |
8 |
11 |
3 |
4 |
-1 |
5 |
7 |
6 |
8 |
11 |
-1 |
3 |
4 |
5 |
6 |
7 |
8 |
11 |
-1 |
3 |
4 |
5 |
6 |
7 |
8 |
11 |
-1 |
3 |
4 |
5 |
6 |
7 |
8 |
11 |
-
In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller
-
This continues until arrays of size 1 are reached, at which point the entire array is sorted
Quicksort: Partition
6 |
5 |
7 |
3 |
4 |
11 |
8 |
-1 |
-
We want to divide the array into smaller and larger parts and put the pivot in between them
-
If we see a smaller value, increase the size of the smaller part and put the value in the smaller part
-
When we’re done, we’ll know where to put the pivot
Quicksort: Partition
6 |
5 |
7 |
3 |
4 |
11 |
8 |
-1 |
|
↑ |
|
|
|
|
|
|
-
We want to divide the array into smaller and larger parts and put the pivot in between them
-
If we see a smaller value, increase the size of the smaller part and put the value in the smaller part
-
When we’re done, we’ll know where to put the pivot
Quicksort: Partition
6 |
5 |
7 |
3 |
4 |
11 |
8 |
-1 |
|
|
↑ |
|
|
|
|
|
-
We want to divide the array into smaller and larger parts and put the pivot in between them
-
If we see a smaller value, increase the size of the smaller part and put the value in the smaller part
-
When we’re done, we’ll know where to put the pivot
Quicksort: Partition
6 |
5 |
7 |
3 |
4 |
11 |
8 |
-1 |
|
|
↑ |
|
|
|
|
|
-
We want to divide the array into smaller and larger parts and put the pivot in between them
-
If we see a smaller value, increase the size of the smaller part and put the value in the smaller part
-
When we’re done, we’ll know where to put the pivot
Quicksort: Partition
6 |
5 |
3 |
7 |
4 |
11 |
8 |
-1 |
|
|
|
↑ |
|
|
|
|
-
We want to divide the array into smaller and larger parts and put the pivot in between them
-
If we see a smaller value, increase the size of the smaller part and put the value in the smaller part
-
When we’re done, we’ll know where to put the pivot
Quicksort: Partition
6 |
5 |
3 |
4 |
7 |
11 |
8 |
-1 |
|
|
|
|
↑ |
|
|
|
-
We want to divide the array into smaller and larger parts and put the pivot in between them
-
If we see a smaller value, increase the size of the smaller part and put the value in the smaller part
-
When we’re done, we’ll know where to put the pivot
Quicksort: Partition
6 |
5 |
3 |
4 |
7 |
11 |
8 |
-1 |
|
|
|
|
↑ |
|
|
|
-
We want to divide the array into smaller and larger parts and put the pivot in between them
-
If we see a smaller value, increase the size of the smaller part and put the value in the smaller part
-
When we’re done, we’ll know where to put the pivot
Quicksort: Partition
6 |
5 |
3 |
4 |
7 |
11 |
8 |
-1 |
|
|
|
|
↑ |
|
|
|
-
We want to divide the array into smaller and larger parts and put the pivot in between them
-
If we see a smaller value, increase the size of the smaller part and put the value in the smaller part
-
When we’re done, we’ll know where to put the pivot
Quicksort: Partition
6 |
5 |
3 |
4 |
-1 |
11 |
8 |
7 |
|
|
|
|
|
↑ |
|
|
-
We want to divide the array into smaller and larger parts and put the pivot in between them
-
If we see a smaller value, increase the size of the smaller part and put the value in the smaller part
-
When we’re done, we’ll know where to put the pivot
Quicksort: Partition
-1 |
5 |
3 |
4 |
6 |
11 |
8 |
7 |
|
|
|
|
|
↑ |
|
|
-
We want to divide the array into smaller and larger parts and put the pivot in between them
-
If we see a smaller value, increase the size of the smaller part and put the value in the smaller part
-
When we’re done, we’ll know where to put the pivot
Quicksort: Partition
-1 |
5 |
3 |
4 |
6 |
11 |
8 |
7 |
|
|
|
|
|
↑ |
|
|
-
We want to divide the array into smaller and larger parts and put the pivot in between them
-
If we see a smaller value, increase the size of the smaller part and put the value in the smaller part
-
When we’re done, we’ll know where to put the pivot
> Click or hit Control-Enter to run the code above
Quicksort Runtime: Best Case
Let’s consider an array of size 8. In the best case, the pivot divides the array evenly at each step. So the analysis is similar to Mergesort:
-
Partition 1: 1 O(n) partition where n = 8 into two arrays of size 4
-
Partition 2: 2 O(n) partition where n = 4 into four arrays of size 2
-
Partition 3: 4 O(n) partition where n = 2 into eight arrays of size 1
-
So given n = 8, we have done 3 O(n) steps, or O(n log n).
But Trouble Lurks…
Quicksort Runtime: Worst Case
Let’s consider an array of size 8. In the worst case, the pivot is the maximum or minimum value in each step.
-
Partition 1: 1 O(n) partition where n = 8 into two arrays of size 7 and size 1
-
Partition 2: 1 O(n) partition where n = 7 into two arrays of size 6 and size 1
-
Partition 3: 1 O(n) partition where n = 6 into two arrays of size 5 and size 1
-
Partition 4: 1 O(n) partition where n = 5 into two arrays of size 4 and size 1
-
…etc…
-
So given n = 8, we have done n O(n) steps, or O(n^2)!
Quicksort: Worst Case Overview
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
-
In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
-
In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
7 |
6 |
5 |
4 |
3 |
2 |
1 |
8 |
-
In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
7 |
6 |
5 |
4 |
3 |
2 |
1 |
8 |
-
In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
6 |
5 |
4 |
3 |
2 |
1 |
7 |
8 |
-
In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
6 |
5 |
4 |
3 |
2 |
1 |
7 |
8 |
-
In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
6 |
5 |
4 |
3 |
2 |
1 |
7 |
8 |
-
In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
5 |
4 |
3 |
2 |
1 |
6 |
7 |
8 |
-
In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
5 |
4 |
3 |
2 |
1 |
6 |
7 |
8 |
-
In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
5 |
4 |
3 |
2 |
1 |
6 |
7 |
8 |
-
In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
4 |
3 |
2 |
1 |
5 |
6 |
7 |
8 |
-
In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
4 |
3 |
2 |
1 |
5 |
6 |
7 |
8 |
-
In the worst case the problem only gets 1 unit smaller in each step!
Avoiding Bad Pivots
Good Quicksort implementations try to avoid picking bad pivot values:
-
First value: fails if the array is sorted in reverse order
-
Last value: fails if the array in already sorted
-
Better idea: choose a random value, or the median of several values
Quicksort Runtime
| Measure | Best Case | Worst Case | Average Case |
|---|---|---|---|
Time |
O(n log n) |
O(n^2) |
O(n log n) |
Space |
O(log n) |
O(n) |
O(log n) |
One advantage of Quicksort over Mergesort is that it can be done in-place without requiring extra space.
Sorting Summary: Input Dependence
| Algorithm | Best Case | Worst Case |
|---|---|---|
Insertion Sort |
Already sorted |
Sorted backwards |
Merge Sort |
Doesn’t matter |
Doesn’t matter |
Quicksort |
Random |
Sorted 1 |
(Note that most of these are implementation dependent.)
Sorting Summary: Runtime
| Algorithm | Best Case | Worst Case | Average Case |
|---|---|---|---|
Insertion Sort |
O(n) |
O(n^2) |
O(n^2) |
Merge Sort |
O(n log n) |
O(n log n) |
O(n log n) |
Quicksort |
O(n log n) |
O(n^2) |
O(n log n) |
Sorting Summary: Space
| Algorithm | Extra Memory |
|---|---|
Insertion Sort |
O(1) |
Merge Sort |
O(n) |
Quicksort |
O(log n), due to the recursive calls |
There Be Tradeoffs
-
If you have a very small array? Try insertion sort. It avoids the recursive calls made by merge sort and quick sort and is fastest on small arrays.
-
Do you want predictable performance? Try merge sort. It’s performance doesn’t vary based on its inputs, although it requires O(n) space.
-
Are you short on space? Try Quicksort. It’s best-case performance is as good as merge sort but it can be done using much less memory.
Sorting Stability
We also refer to sorts as being either stable or unstable:
-
Stable sorts: two items with the same value cannot switch positions
-
Unstable sorts: two items with the same value may switch positions
Why Is Stability Important?
class Person {
int age;
String name;
}Let’s say I wanted a list of all Persons, sorted first by age and then by
name. How would I do that?
-
Sort first using the
namefield -
Then sort by the
agefield
If the sort is not stable I cannot do this, since the second sort will alter the results of the first.
What About Timsort?
Timsort is the adaptive sorting algorithm used by Python and now Java.
-
It’s far more complex than any of the algorithms we’ve discussed, but tries to take advantage of runs of already-sorted values in the data.
-
Internally it uses both merge sort and insertion sort to sort smaller arrays and combine them together.
-
It’s an adaptive sort, meaning that it adjusts its behavior to features of the data.
A Fun Visualization
Questions About Sorting?
Announcements
-
I’m still holding office hours online, but nobody ever comes. Please drop in and say hi!