Insertion Sort and Quicksort
1
Lecture 30 (Sorting 2)
CS61B, Fall 2024 @ UC Berkeley
Slides credit: Josh Hug
Final exam review session:
Friday, November 8, 11:00 AM - 1:30PM
2nd floor Soda Labs (rooms 273, 275, and 277)
Naive Insertion Sort
Lecture 30, CS61B, Fall 2024
Insertion Sort
Miscellaneous Sorts
Quicksort
Insertion Sort
General strategy:
Naive approach, build entirely new output: Demo (Link)
32
15
2
17
19
26
41
17
17
Input:
Output:
Insertion Sort
General strategy:
Naive approach, build entirely new output:
32
15
2
17
19
26
41
17
17
Input:
Output:
Insertion Sort
General strategy:
Naive approach, build entirely new output:
32
15
2
17
19
26
41
17
17
32
Input:
Output:
Insertion Sort
General strategy:
Naive approach, build entirely new output:
32
15
2
17
19
26
41
17
17
32
15
Input:
Output:
Insertion Sort
General strategy:
Naive approach, build entirely new output:
32
15
2
17
19
26
41
17
17
32
15
2
Input:
Output:
Insertion Sort
General strategy:
Naive approach, build entirely new output:
32
15
2
17
19
26
41
17
17
32
15
2
17
Input:
Output:
Insertion Sort
General strategy:
Naive approach, build entirely new output:
32
15
2
17
19
26
41
17
17
32
15
2
17
19
Input:
Output:
Insertion Sort
General strategy:
Naive approach, build entirely new output:
32
15
2
17
19
26
41
17
17
32
15
2
17
19
26
Input:
Output:
Insertion Sort
General strategy:
Naive approach, build entirely new output:
32
15
2
17
19
26
41
17
17
32
15
2
17
19
26
41
Input:
Output:
Insertion Sort
General strategy:
Naive approach, build entirely new output:
32
15
2
17
19
26
41
17
17
32
15
2
17
19
26
41
17
Input:
Output:
Insertion Sort
General strategy:
Naive approach, build entirely new output:
32
15
2
17
19
26
41
17
17
32
15
2
17
19
26
41
17
17
Input:
Output:
In-Place Insertion Sort
Lecture 30, CS61B, Fall 2024
Insertion Sort
Miscellaneous Sorts
Quicksort
Insertion Sort
General strategy:
For naive approach, if output sequence contains k items, worst cost to insert a single item is k.
More efficient method:
In-place Insertion Sort
General strategy:
32
15
2
17
19
26
41
17
17
In example above: Use j pointer to track current spot of traveling item.
Input:
In-place Insertion Sort
General strategy:
32
15
2
17
19
26
41
17
17
i
j
In example above: Use j pointer to track current spot of traveling item.
Input:
In-place Insertion Sort
General strategy:
32
15
2
17
19
26
41
17
17
i
j
sorted
unexamined
In example above: Use j pointer to track current spot of traveling item.
Input:
In-place Insertion Sort
General strategy:
32
15
2
17
19
26
41
17
17
i
j
sorted
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
15
32
2
17
19
26
41
17
17
i
j
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
15
32
2
17
19
26
41
17
17
i
j
sorted
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
15
32
2
17
19
26
41
17
17
i
j
sorted
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
15
2
32
17
19
26
41
17
17
i
j
Note: We’ve temporarily broken our invariant that the items up through item i should be sorted!
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
2
15
32
17
19
26
41
17
17
i
j
Once the traveller settles, the invariant is restored.
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
2
15
32
17
19
26
41
17
17
i
j
sorted
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
2
15
32
17
19
26
41
17
17
i
j
sorted
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
2
15
17
32
19
26
41
17
17
i
j
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
2
15
17
32
19
26
41
17
17
i
j
sorted
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
2
15
17
32
19
26
41
17
17
j
sorted
i
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
2
15
17
19
32
26
41
17
17
i
j
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
2
15
17
19
32
26
41
17
17
i
j
sorted
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
2
15
17
19
32
26
41
17
17
i
j
sorted
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
2
15
17
19
26
32
41
17
17
i
j
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
2
15
17
19
26
32
41
17
17
i
j
sorted
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
2
15
17
19
26
32
41
17
17
i
j
sorted
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
2
15
17
19
26
32
41
17
17
i
j
sorted
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
2
15
17
19
26
32
41
17
17
i
j
sorted
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
2
15
17
19
26
32
17
41
17
i
j
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
2
15
17
19
26
17
32
41
17
i
j
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
2
15
17
19
17
26
32
41
17
i
j
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
2
15
17
17
19
26
32
41
17
i
j
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
2
15
17
17
19
26
32
41
17
i
j
sorted
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
2
15
17
17
19
26
32
41
17
i
j
sorted
In example above: Use j pointer to track current spot of traveling item.
unexamined
Input:
In-place Insertion Sort
General strategy:
2
15
17
17
19
26
32
17
41
i
j
In example above: Use j pointer to track current spot of traveling item.
Input:
In-place Insertion Sort
General strategy:
2
15
17
17
19
26
17
32
41
i
j
In example above: Use j pointer to track current spot of traveling item.
Input:
In-place Insertion Sort
General strategy:
2
15
17
17
19
17
26
32
41
i
j
In example above: Use j pointer to track current spot of traveling item.
Input:
In-place Insertion Sort
General strategy:
2
15
17
17
17
19
26
32
41
i
j
In example above: Use j pointer to track current spot of traveling item.
Input:
In-place Insertion Sort
General strategy:
2
15
17
17
17
19
26
32
41
Input:
i
j
In example above: Use j pointer to track current spot of traveling item.
sorted
Insertion Sort Runtime
Lecture 30, CS61B, Fall 2024
Insertion Sort
Miscellaneous Sorts
Quicksort
In-place Insertion Sort
Two more examples.
7 swaps:
36 swaps:
P O T A T O
P O T A T O (0 swaps)
O P T A T O (1 swap )
O P T A T O (0 swaps)
A O P T T O (3 swaps)
A O P T T O (0 swaps)
A O O P T T (3 swaps)
S O R T E X A M P L E
S O R T E X A M P L E (0 swaps)
O S R T E X A M P L E (1 swap )
O R S T E X A M P L E (1 swap )
O R S T E X A M P L E (0 swaps)
E O R S T X A M P L E (4 swaps)
E O R S T X A M P L E (0 swaps)
A E O R S T X M P L E (6 swaps)
A E M O R S T X P L E (5 swaps)
A E M O P R S T X L E (4 swaps)
A E L M O P R S T X E (7 swaps)
A E E L M O P R S T X (8 swaps)
Purple: Element that we’re moving left (with swaps).
Black: Elements that got swapped with purple.
Grey: Not considered this iteration.
Insertion Sort Runtime: yellkey.com/TODO
What is the runtime of insertion sort?
36 swaps:
Insertion Sort Runtime
What is the runtime of insertion sort?
You may recall Ω is not “best case”.
So technnnniically you could also say � Ω(1)
36 swaps:
Picking the Best Sort: yellkey.com/TODO
Suppose we do the following:
Which sorting algorithm would be the fastest choice for X?
Recall: Inversions
An inversion is a pair of elements that are out of order with respect to <.
Another way to state the goal of sorting:
(9 choose 2) = 45 inversions at most
2
15
17
19
26
17
32
41
17
Recall: Inversions
An inversion is a pair of elements that are out of order with respect to <.
Another way to state the goal of sorting:
19-17
(out of 45 inversions)
2
15
17
19
26
17
32
41
17
Recall: Inversions
An inversion is a pair of elements that are out of order with respect to <.
Another way to state the goal of sorting:
19-17, 19-17
(out of 45 inversions)
2
15
17
19
26
17
32
41
17
Recall: Inversions
An inversion is a pair of elements that are out of order with respect to <.
Another way to state the goal of sorting:
19-17, 19-17, 26-17
(out of 45 inversions)
2
15
17
19
26
17
32
41
17
Recall: Inversions
An inversion is a pair of elements that are out of order with respect to <.
Another way to state the goal of sorting:
19-17, 19-17, 26-17, 26-17
(out of 45 inversions)
2
15
17
19
26
17
32
41
17
Recall: Inversions
An inversion is a pair of elements that are out of order with respect to <.
Another way to state the goal of sorting:
19-17, 19-17, 26-17, 26-17
32-17
(out of 45 inversions)
2
15
17
19
26
17
32
41
17
Recall: Inversions
An inversion is a pair of elements that are out of order with respect to <.
Another way to state the goal of sorting:
19-17, 19-17, 26-17, 26-17
32-17, 41-17 = 6 total inversions
(out of 45 inversions)
2
15
17
19
26
17
32
41
17
Observation: Each swap in Insertion Sort reduces the number of inversions by 1
Inversions between red items don't change (because they don't move)
Inversions between a red and blue item don't change (their relative position in the array stays the same)
We fix one inversion within the blue items
So total number of inversions decrease by 1 every swap
2
15
17
19
26
17
32
41
17
i
j
2
15
17
19
17
26
32
41
17
i
j
Observation: Insertion Sort on Almost Sorted Arrays
For arrays that are almost sorted, insertion sort does very little work.
Picking the Best Sort (Poll Everywhere)
Suppose we do the following:
Which sorting algorithm would be the fastest choice for X? Worst case run-times:
Insertion Sort Sweet Spots
On arrays with a small number of inversions, insertion sort is extremely fast.
Less obvious: For small arrays (N < 15 or so), insertion sort is fastest.
Sorts So Far
| Best Case Runtime | Worst Case Runtime | Space | Demo | Notes |
Θ(N2) | Θ(N2) | Θ(1) | | ||
(in place) | Θ(N)* | Θ(N log N) | Θ(1) | Bad cache (61C) performance. | |
Θ(N log N) | Θ(N log N) | Θ(N) | Fastest of these. | ||
Insertion Sort (in place) | Θ(N) | Θ(N2) | Θ(1) | Best for small N or almost sorted. |
See this link for bonus slides on Shell's Sort, an optimization of insertion sort.
Miscellaneous Sorts
Lecture 30, CS61B, Fall 2024
Insertion Sort
Miscellaneous Sorts
Quicksort
A lightning round of other sorting algorithms
There are many sorting algorithms. Not all of them are actually useful, but they still get referenced every now and then.
We haven't yet covered the fastest sorting algorithms. But before we do that, let's go over a few other sorting algorithms.
Adaptive Sorting Algorithms
On arrays with a small number of inversions, insertion sort is extremely fast.
More generally, we can think of sorting algorithms that behave like this:
Step 2 fixes one inversion each time, so we get Θ(K) time from that step
Step 1 in insertion sort looks at and solves the inversions of one item at a time, and takes Θ(N+K) in total (since we check N+K total pairs for inversions).
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
32
15
2
17
19
26
41
17
17
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
32
15
2
17
19
26
41
17
17
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
15
32
2
17
19
26
41
17
17
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
15
2
32
17
19
26
41
17
17
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
15
2
17
32
19
26
41
17
17
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
15
2
17
19
32
26
41
17
17
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
15
2
17
19
26
32
41
17
17
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
15
2
17
19
26
32
41
17
17
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
15
2
17
19
26
32
17
41
17
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
15
2
17
19
26
32
17
17
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
2
15
17
19
26
32
17
17
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
2
15
17
19
26
32
17
17
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
2
15
17
19
26
32
17
17
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
2
15
17
19
26
32
17
17
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
2
15
17
19
26
32
17
17
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
2
15
17
19
26
17
32
17
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
2
15
17
19
26
17
17
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
2
15
17
19
26
17
17
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
2
15
17
19
26
17
17
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
2
15
17
19
26
17
17
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
2
15
17
19
26
17
17
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
2
15
17
19
26
17
17
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
2
15
17
19
17
26
17
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
2
15
17
19
17
17
26
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
2
15
17
19
17
17
26
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
2
15
17
19
17
17
26
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
2
15
17
19
17
17
26
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
2
15
17
19
17
17
26
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
2
15
17
19
17
17
26
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
2
15
17
17
19
17
26
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
(At this point, the list is sorted, but we run through the list one more time to confirm that)
2
15
17
17
17
19
26
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
(At this point, the list is sorted, but we run through the list one more time to confirm that)
2
15
17
17
17
19
26
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
(At this point, the list is sorted, but we run through the list one more time to confirm that)
2
15
17
17
17
19
26
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
(At this point, the list is sorted, but we run through the list one more time to confirm that)
2
15
17
17
17
19
26
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
(At this point, the list is sorted, but we run through the list one more time to confirm that)
2
15
17
17
17
19
26
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
(At this point, the list is sorted, but we run through the list one more time to confirm that)
2
15
17
17
17
19
26
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
(At this point, the list is sorted, but we run through the list one more time to confirm that)
2
15
17
17
17
19
26
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
(At this point, the list is sorted, but we run through the list one more time to confirm that)
2
15
17
17
17
19
26
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
(At this point, the list is sorted, but we run through the list one more time to confirm that)
2
15
17
17
17
19
26
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
(At this point, the list is sorted, but we run through the list one more time to confirm that)
2
15
17
17
17
19
26
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
(At this point, the list is sorted, but we run through the list one more time to confirm that)
2
15
17
17
17
19
26
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort:
Iterate through the list and look at each adjacent pair
If the two elements are in a wrong order, swap them
Repeat iterating through list until the array is sorted
2
15
17
17
17
19
26
32
41
Input:
Bad sorting algorithm: Bubble sort
Bubble sort is the same as insertion sort, except it doesn't find inversions as quickly.
Very slow in theory, and slow in practice too (~5x slower than insertion sort)
Items that need to move left are "turtles" that take a long time to move to the right spot.
Other variations of insertion sort:
Shuffling
Let's try solving the "reverse" problem to sorting: Shuffling
Given a list of n elements and a random number generator, return a random permutation (reordering) of the list.
The random number generator receives as input two integers i and j, and returns a random integer between i and j.
Goals:
1
2
3
4
5
6
7
8
9
Input:
Shuffling
For each number i from 0 to n-1:
1
2
3
4
5
6
7
8
9
Input:
Shuffling
For each number i from 0 to n-1:
1
2
3
4
5
6
7
8
9
Input:
i
Shuffling
For each number i from 0 to n-1:
7
2
3
4
5
6
1
8
9
Input:
i
Shuffling
For each number i from 0 to n-1:
7
2
3
4
5
6
1
8
9
Input:
i
Shuffling
For each number i from 0 to n-1:
7
9
3
4
5
6
1
8
2
Input:
i
Shuffling
For each number i from 0 to n-1:
7
9
3
4
5
6
1
8
2
Input:
i
Shuffling
For each number i from 0 to n-1:
7
9
3
4
5
6
1
8
2
Input:
i
Shuffling
For each number i from 0 to n-1:
(Remaining Steps omitted)
7
9
3
4
5
6
1
8
2
Input:
i
Shuffling
For each number i from 0 to n-1:
7
9
3
1
2
4
6
5
8
Input:
i
Shuffling
For each number i from 0 to n-1:
Runtime?
7
9
3
1
2
4
6
5
8
Input:
i
Shuffling
For each number i from 0 to n-1:
Runtime? Θ(n) (We do n iterations of constant time each)
Even distribution?
7
9
3
1
2
4
6
5
8
Input:
i
Shuffling
For each number i from 0 to n-1:
Runtime? Θ(n)
Even distribution? Perfectly even (Each permutation has exactly one way of being created, with probability 1/n * 1/(n-1) * … * (1/1) = 1/(n!)
7
9
3
1
2
4
6
5
8
Input:
i
Bad sorting algorithm: BOGO sort
BOGO sort:
While list is not sorted: (O(n) time to check if list is sorted)
Let's analyze this quickly:
Best-case runtime:
Worst-case runtime:
Average runtime:
Bad sorting algorithm: BOGO sort
Here's a bad sorting algorithm:
While list is not sorted: (O(n) time to check if list is sorted)
Let's analyze this quickly:
Best-case runtime: Θ(n) (if the list is sorted initially)
Worst-case runtime: Infinite runtime (if we never shuffle it the right way)
Average runtime: Θ(n*n!) (while loop has on average n! iterations before we get the sorted order)
Quicksort Backstory, Partitioning
Lecture 30, CS61B, Fall 2024
Insertion Sort
Miscellaneous Sorts
Quicksort
Sorts So Far
| Best Case Runtime | Worst Case Runtime | Space | Demo | Notes |
Θ(N2) | Θ(N2) | Θ(1) | | ||
(in place) | Θ(N)* | Θ(N log N) | Θ(1) | Bad cache (61C) performance. | |
Θ(N log N) | Θ(N log N) | Θ(N) | Fastest of these. | ||
Insertion Sort (in place) | Θ(N) | Θ(N2) | Θ(1) | Best for small N or almost sorted. |
Sorting So Far
Core ideas:
Quicksort:
Context for Quicksort’s Invention (Source)
1960: Tony Hoare was working on a crude automated translation program for Russian and English. �
... | ... |
beautiful | красивая |
... | ... |
cat | кошка |
... | ... |
“The cat wore a beautiful hat.”
Dictionary of D english words
N words
“Кошка носил красивая шапка.”
How would you do this?
Context for Quicksort’s Invention (Source)
Limitation at the time:
1960: Tony Hoare was working on a crude automated translation program for Russian and English.
Algorithm: N binary searches of D length dictionary.
... | ... |
beautiful | красивая |
... | ... |
cat | кошка |
... | ... |
Partitioning
Main idea: I have a list of small and large items. To sort this:
How to decide what's big and what's small?
We'll call this a partition; we separate the big items and the small items, and put remaining items in the middle.
Partitioning
A partition of an array, given a pivot x, is a rearrangement of the items so that:
3
1
2
4
6
8
7
3
4
1
2
6
7
8
Example of a valid output
Another example of a valid output
6
8
3
1
2
7
4
Input
9
9
9
Core Idea of Tony’s Sort: Partitioning http://yellkey.com/TODO
A partition of an array, given a pivot x, is a rearrangement of the items so that:
Which partitions are valid?
5
550
10
4
10
9
330
4
5
9
10
10
330
550
5
9
10
4
10
550
330
5
4
9
10
10
550
330
5
9
10
4
10
550
330
A.
C.
B.
D.
j
j
j
j
The Core Idea of Tony’s Sort: Partitioning
A partition of an array, given a pivot x, is a rearrangement of the items so that:
Which partitions are valid?
5
550
10
4
10
9
330
i
4
5
9
10
10
330
550
5
9
10
4
10
550
330
5
4
9
10
10
550
330
5
9
10
4
10
550
330
A.
C.
B.
D.
j
j
j
j
Called the ‘pivot’.
Job Interview Style Question (Partitioning)
Given an array of colors where the 0th element is white (and maybe a few more), and the remaining elements are red (less) or blue (greater), rearrange the array so that all red squares are to the left of the white square, the white squares end up together, and all blue squares are to the right. Your algorithm must complete in Θ(N) time (no space restriction).
3
1
2
4
6
8
7
3
4
1
2
6
7
8
Example of a valid output
Another example of a valid output
6
8
3
1
2
7
4
Input
6
6
6
Quicksort
Lecture 30, CS61B, Fall 2024
Insertion Sort
Miscellaneous Sorts
Quicksort
Partition Sort, a.k.a. Quicksort
Observations:
5
3
2
1
8
4
6
7
3
2
1
4
7
8
6
5
3
2
1
4
5
7
8
6
5
2
1
3
4
5
6
7
8
5
Q: How would we use this operation for sorting?
Quick Sort
Quick sorting N items:
32
15
2
17
19
26
41
17
17
Input:
unsorted
Quick Sort
Quick sorting N items:
32
15
2
17
19
26
41
17
17
Input:
partition(32)
Quick Sort
Quick sorting N items:
15
2
17
19
26
17
17
32
41
Input:
<= 32
>= 32
in its place
partition(32)
Quick Sort
Quick sorting N items:
15
2
17
19
26
17
17
32
Input:
in its place
41
partition(32)
Quick Sort
Quick sorting N items:
partition(32)
partition(15)
partition(2)
partition(17)
partition(19)
partition(17)
partition(17)
partition(26)
x
x
x
x
x
x
x
2
15
17
17
17
19
26
32
41
Input:
in its place
in its place
in its place
in its place
in its place
in its place
in its place
in its place
x
Quick Sort
Quick sorting N items:
partition(32)
partition(15)
partition(2)
partition(17)
partition(19)
partition(17)
partition(17)
partition(26)
x
x
x
x
x
x
x
2
15
17
17
17
19
26
32
41
Input:
in its place
in its place
in its place
in its place
in its place
in its place
in its place
in its place
in its place
If you don't fully trust the recursion, see these extra slides for a complete demo.
x
Partition Sort, a.k.a. Quicksort
Quick sorting N items:
32
15
2
17
19
26
41
17
17
partition(32)
15
2
17
19
26
17
17
32
41
<= 32
>= 32
in its place
Quicksort
Quicksort was the name chosen by Tony Hoare for partition sort.
How fast is Quicksort? Need to count number and difficulty of partition operations.
Theoretical analysis: