Today’s Musical Selections
Our second video with a self-driving car as a metaphor? "Call it Dreaming" by Iron and Wine.
I hope you all have a bit of time for dreaming during these dark days.
Insertion and Merge Sort
> Click or hit Control-Enter to run the code above
Sorting Algorithms
Sorting algorithms bring together several of the things that we have discussed recently:
-
Imperative programming
-
Big-O algorithm runtime analysis
-
Recursion
Sorting Matters
Sorting is often a building block for many other algorithms.
-
Searching is more efficient if the data is sorted first
-
Sorting can be used to detect duplicates
-
Sorting is often used to produce a canonical representation of data or for presentation to human users
In Memory of Jim Gray, Turing Award Winner
Jim Gray was a pioneer in the fields of databases and data processing.
He vanished at seat in 2007 and, despite a worldwide crowdsourced effort to locate his boat, was never found.
There Are Many Sorting Algorithms
And we won’t discuss them all…
-
Insertion sort (today)
-
Selection sort (lab)
-
Merge sort (today)
-
Quicksort (Monday)
-
Bubble sort (lab)
-
And even new ones, like Timsort (circa 2002)
Insertion Sort: Overview
8 |
5 |
7 |
3 |
4 |
11 |
6 |
-1 |
-
Insertion sort divides the array into two parts: a sorted part and an unsorted part
-
The sorted part starts at the beginning of the array and grows during each step
Insertion Sort: Overview
8 |
5 |
7 |
3 |
4 |
11 |
6 |
-1 |
8 |
5 |
7 |
3 |
4 |
11 |
6 |
-1 |
5 |
8 |
7 |
3 |
4 |
11 |
6 |
-1 |
5 |
7 |
8 |
3 |
4 |
11 |
6 |
-1 |
3 |
5 |
7 |
8 |
4 |
11 |
6 |
-1 |
3 |
4 |
5 |
7 |
8 |
11 |
6 |
-1 |
3 |
4 |
5 |
7 |
8 |
11 |
6 |
-1 |
3 |
4 |
5 |
6 |
7 |
8 |
11 |
-1 |
-1 |
3 |
4 |
5 |
6 |
7 |
8 |
11 |
-
Insertion sort divides the array into two parts: a sorted part and an unsorted part
-
The sorted part starts at the beginning of the array and grows during each step
Insertion Sort: Insertion
8 |
5 |
7 |
3 |
4 |
11 |
6 |
-1 |
8 |
5 |
7 |
3 |
4 |
11 |
6 |
-1 |
5 |
8 |
7 |
3 |
4 |
11 |
6 |
-1 |
5 |
7 |
8 |
3 |
4 |
11 |
6 |
-1 |
3 |
5 |
7 |
8 |
4 |
11 |
6 |
-1 |
3 |
4 |
5 |
7 |
8 |
11 |
6 |
-1 |
3 |
4 |
5 |
7 |
8 |
11 |
6 |
-1 |
3 |
4 |
5 |
6 |
7 |
8 |
11 |
-1 |
-1 |
3 |
4 |
5 |
6 |
7 |
8 |
11 |
-
In each step we take the first item from the unsorted region and insert it in the right place in the sorted region
Insertion Sort: A Single Step
3 |
4 |
5 |
7 |
8 |
11 |
6 |
-1 |
-
Let’s look at one step in more detail
Insertion Sort: A Single Step
|
|
|
|
|
|
6 |
|
3 |
4 |
5 |
7 |
8 |
11 |
|
-1 |
-
Let’s look at one step in more detail
Insertion Sort: A Single Step
|
|
|
|
|
6 |
|
|
3 |
4 |
5 |
7 |
8 |
11 |
|
-1 |
-
Let’s look at one step in more detail
Insertion Sort: A Single Step
|
|
|
|
|
6 |
|
|
3 |
4 |
5 |
7 |
8 |
|
11 |
-1 |
-
Let’s look at one step in more detail
Insertion Sort: A Single Step
|
|
|
|
|
6 |
|
|
3 |
4 |
5 |
7 |
|
8 |
11 |
-1 |
-
Let’s look at one step in more detail
Insertion Sort: A Single Step
|
|
|
|
6 |
|
|
|
3 |
4 |
5 |
7 |
|
8 |
11 |
-1 |
-
Let’s look at one step in more detail
Insertion Sort: A Single Step
|
|
|
|
6 |
|
|
|
3 |
4 |
5 |
|
7 |
8 |
11 |
-1 |
-
Let’s look at one step in more detail
Insertion Sort: A Single Step
|
|
|
6 |
|
|
|
|
3 |
4 |
5 |
|
7 |
8 |
11 |
-1 |
-
Let’s look at one step in more detail
Insertion Sort: A Single Step
3 |
4 |
5 |
6 |
7 |
8 |
11 |
-1 |
-
Let’s look at one step in more detail
> Click or hit Control-Enter to run the code above
Insertion Sort Runtime
Time complexity:
-
Worst case: O(n^2) if the array is sorted in descending order (for this implementation)
-
Best case: O(n) if the array is already sorted (for this implementation)
-
Average case: O(n^2)
Space complexity: can be done in place with one temporary variable, so O(1)
Insertion Sort Runtime
| Measure | Best Case | Worst Case | Average Case |
|---|---|---|---|
Time |
O(n) |
O(n^2) |
O(n^2) |
Space |
O(1) |
O(1) |
O(1) |
We Can Do Better
Optimal sorting algorithms should be O(n log n) in the worst case and close to O(n) in the best case.
Java Generics (Brief Digression)
Lists are one of the two data structures you meet in heaven.
We’ve studied them in class together. But you’ll usually use Java`s built-in implementations.
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
List list = new ArrayList();
List anotherList = new LinkedList();> Click or hit Control-Enter to run Example.main above
Compiler Errors v. Runtime Errors
Java and many languages that followed it have tried to transform runtime errors into compiler errors. Why?
-
You compile your code before it runs: and so before you have to demo it to a client, or before you deploy it to hundreds of users.
-
Catching errors at this stage is critical.
Generics
Java generics allow us to create reusable classes while allowing the compiler to check our code for correctness.
import java.util.List;
import java.util.ArrayList;
List<Integer> integerlist = new ArrayList<Integer>(); // This is list of Integers
List<String> stringList = new ArrayList<String>(); // This is a list of Strings> Click or hit Control-Enter to run Example.main above
We’ll Return to Generics
And talk about how to use them in your own classes. But that’s all for today.
Spring 2020 CS 125 Grading Changes
Announcements
-
We’ve made some scheduling updates for office hours. Virtual office hours will now run 8–10AM and then from 2–6PM, to better accommodate students in a mix of time zones.
-
Have a great weekend!