Quicksort
> Click or hit Control-Enter to run the code above
There Are Many Sorting Algorithms
And we won’t discuss them all…
-
Insertion sort (last Wednesday)
-
Selection sort (lab)
-
Merge sort (last Friday)
-
Quicksort (today!)
-
Bubble sort (lab)
Merge Runtime
Time complexity:
-
Worst case: O(n)
-
Best case: O(n)
-
Average case: O(n)
But What About Mergesort?
Array Recursion
1 |
10 |
5 |
6 |
4 |
11 |
7 |
-1 |
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 |
10 |
5 |
6 |
4 |
11 |
7 |
-1 |
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 |
10 |
5 |
6 |
4 |
11 |
7 |
-1 |
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 |
10 |
5 |
6 |
4 |
11 |
7 |
-1 |
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 |
10 |
5 |
6 |
4 |
11 |
7 |
-1 |
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 |
10 |
5 |
6 |
4 |
11 |
7 |
-1 |
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 |
10 |
5 |
6 |
4 |
11 |
7 |
-1 |
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 |
10 |
5 |
6 |
4 |
11 |
7 |
-1 |
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 |
10 |
5 |
6 |
4 |
11 |
7 |
-1 |
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 |
10 |
5 |
6 |
4 |
11 |
7 |
-1 |
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 |
10 |
5 |
6 |
4 |
11 |
7 |
-1 |
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 |
10 |
5 |
6 |
4 |
11 |
7 |
-1 |
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 |
10 |
5 |
6 |
4 |
11 |
7 |
-1 |
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 |
10 |
5 |
6 |
4 |
11 |
7 |
-1 |
Each contiguous subarray of an array is, itself, an array.
Array Recursion
Just like with trees and lists, we need a way to both make the problem smaller and identify the smallest subproblem.
-
How do we make the problem smaller? Break the list into two smaller subarrays.
-
What’s the smallest subproblem? An array with a single item.
What’s Our (Recursive) Sorting Algorithm?
Recursive Mergesort
-
Base case: We’ve reached an array with just one value, so return in.
-
Recursive step: Split the array into two roughly equal parts.
-
Combine results: Merge the two smaller subarrays.
> Click or hit Control-Enter to run the code above
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).
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 |
|
|
|
|
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
Announcements
-
The MP4 early deadline is today. Get your 40 points!