Sorting Algorithms
> 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.
Speaking of the Turing Award…
There Are Many Sorting Algorithms
And we won’t discuss them all…
-
Insertion sort (today)
-
Selection sort (lab)
-
Merge sort (lecture)
-
Quicksort (lecture)
-
Bubble sort (lab)
-
And even new ones, like Timsort (circa 2002)
Sorting Basics
-
We’ll discuss sorting on arrays which allow random access, although many algorithms will also work on lists.
-
We’ll be sorting in ascending order, although obviously descending order sorts are also possible.
-
We can sort anything that we can compare—but we’ll mostly be sorting integers.
Analyzing Sorting Algorithms
Since sorting algorithms handle data, we care about both time and space complexity.
-
Time complexity: how long does it take?
-
Space complexity: how much space is required?
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.
Merge Sort: Overview
|
|
|
|
1 |
8 |
9 |
12 |
|
|
|
|
2 |
5 |
7 |
10 |
|
|
|
|
|
|
|
|
-
Merge sort harnesses the fact that it is easy to merge two already-sorted arrays
Merge Sort: Overview
|
|
|
|
1 |
8 |
9 |
12 |
|
|
|
|
2 |
5 |
7 |
10 |
|
|
|
|
|
|
|
|
-
Merge sort harnesses the fact that it is easy to merge two already-sorted arrays
Merge Sort: Overview
|
|
|
|
8 |
9 |
12 |
|
|
|
|
|
2 |
5 |
7 |
10 |
1 |
|
|
|
|
|
|
|
-
Merge sort harnesses the fact that it is easy to merge two already-sorted arrays
Merge Sort: Overview
|
|
|
|
8 |
9 |
12 |
|
|
|
|
|
2 |
5 |
7 |
10 |
1 |
|
|
|
|
|
|
|
-
Merge sort harnesses the fact that it is easy to merge two already-sorted arrays
Merge Sort: Overview
|
|
|
|
8 |
9 |
12 |
|
|
|
|
|
5 |
7 |
10 |
|
1 |
2 |
|
|
|
|
|
|
-
Merge sort harnesses the fact that it is easy to merge two already-sorted arrays
Merge Sort: Overview
|
|
|
|
8 |
9 |
12 |
|
|
|
|
|
5 |
7 |
10 |
|
1 |
2 |
|
|
|
|
|
|
-
Merge sort harnesses the fact that it is easy to merge two already-sorted arrays
Merge Sort: Overview
|
|
|
|
8 |
9 |
12 |
|
|
|
|
|
7 |
10 |
|
|
1 |
2 |
5 |
|
|
|
|
|
-
Merge sort harnesses the fact that it is easy to merge two already-sorted arrays
Merge Sort: Overview
|
|
|
|
8 |
9 |
12 |
|
|
|
|
|
7 |
10 |
|
|
1 |
2 |
5 |
|
|
|
|
|
-
Merge sort harnesses the fact that it is easy to merge two already-sorted arrays
Merge Sort: Overview
|
|
|
|
8 |
9 |
12 |
|
|
|
|
|
10 |
|
|
|
1 |
2 |
5 |
7 |
|
|
|
|
-
Merge sort harnesses the fact that it is easy to merge two already-sorted arrays
Merge Sort: Overview
|
|
|
|
8 |
9 |
12 |
|
|
|
|
|
10 |
|
|
|
1 |
2 |
5 |
7 |
|
|
|
|
-
Merge sort harnesses the fact that it is easy to merge two already-sorted arrays
Merge Sort: Overview
|
|
|
|
9 |
12 |
|
|
|
|
|
|
10 |
|
|
|
1 |
2 |
5 |
7 |
8 |
|
|
|
-
Merge sort harnesses the fact that it is easy to merge two already-sorted arrays
Merge Sort: Overview
|
|
|
|
9 |
12 |
|
|
|
|
|
|
10 |
|
|
|
1 |
2 |
5 |
7 |
8 |
|
|
|
-
Merge sort harnesses the fact that it is easy to merge two already-sorted arrays
Merge Sort: Overview
|
|
|
|
12 |
|
|
|
|
|
|
|
10 |
|
|
|
1 |
2 |
5 |
7 |
8 |
9 |
|
|
-
Merge sort harnesses the fact that it is easy to merge two already-sorted arrays
Merge Sort: Overview
|
|
|
|
12 |
|
|
|
|
|
|
|
10 |
|
|
|
1 |
2 |
5 |
7 |
8 |
9 |
|
|
-
Merge sort harnesses the fact that it is easy to merge two already-sorted arrays
Merge Sort: Overview
|
|
|
|
12 |
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
5 |
7 |
8 |
9 |
10 |
|
-
Merge sort harnesses the fact that it is easy to merge two already-sorted arrays
Merge Sort: Overview
|
|
|
|
12 |
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
5 |
7 |
8 |
9 |
10 |
|
-
Merge sort harnesses the fact that it is easy to merge two already-sorted arrays
Merge Sort: Overview
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
5 |
7 |
8 |
9 |
10 |
12 |
-
Merge sort harnesses the fact that it is easy to merge two already-sorted arrays
Announcements
-
MP5 is due next Monday at 5PM.
-
Get your Android environment set up! Come to office hours if you need help.
-
We’ve added an anonymous feedback form to the course website. Use it to give us feedback!
-
My office hours continue today at 11AM in the lounge outside of Siebel 0226.