Sorting Algorithms
> Click or hit ControlEnter to run the code above
E1 Review: MinMax
Complete the implementation of a public nonfinal class called MinMax
.
MinMax
should provide the following instance methods:

add
: takes a reference to any Java object that implementsComparable
. 
min
: takes no arguments and returns a reference (as aComparable
) to the minimum of all values previously added to the instance usingadd
. If no values have beenadded
it should returnnull
. 
max
takes no arguments and returns a reference (as aComparable
) to the maximum of all values previously added to the instance usingadd
. If no values have beenadded
it should returnnull
.
E1 Review: MinMax
You should compare Comparable
objects using compareTo
.
As a reminder, first.compareTo(second)
returns a positive value if first
is
larger than second
, a negative value if first
is smaller than second
, and
0 if they are equal.
MinMax
should also provide two constructors:

An empty constructor that takes no arguments.

A constructor taking a single reference to a
Comparable
object. This constructor behaves like the empty constructor followed by a call toadd
.
Note that the test suite will always pass the same type of argument to each
MinMax
instance once it has been created.
> Click or hit ControlEnter to run Example.main above
Questions About Midterm 1?
Recursive Tree Traversal
Let’s find all nodes in the tree and add them to a list.
What’s Our (Recursive) Algorithm?
Recursive Tree Traversal

Base case: We’ve reached a
null
node, at which point we can stop. 
Recursive step: Consider our right tree and left tree separately.

Combine results: Add ourselves to the list of nodes.
Java ArrayList
s
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 builtin implementations.
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
List list = new ArrayList();
List anotherList = new LinkedList();
> Click or hit ControlEnter to run the code above
> Click or hit ControlEnter to run Example.main above
Other Recursive Data Structures
Every sub(blank) of a (blank) is, itself, a (blank).

Tree

(Contiguous) List

(Contiguous) Array
But Don’t Recurse on Lists
Just use a loop.
> Click or hit ControlEnter to run Example.main above
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
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.
Sorting Algorithms
Sorting algorithms bring together several of the things that we have discussed recently:

Imperative programming

BigO 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 (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 ControlEnter 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.
Announcements

The early MP5 deadline is next Monday. Please get started!

I now have office hours MWF from 10AM–12PM in Siebel 2227. Please stop by!

Remember to provide feedback on the course using the anonymous feedback form.

I’ve started to respond to existing feedback on the forum.