Sorting Algorithms

Sorting Algorithms
> Click or hit Control-Enter to run the code above

Complete the implementation of a public non-final class called MinMax. MinMax should provide the following instance methods:

add: takes a reference to any Java object that implements Comparable.
min: takes no arguments and returns a reference (as a Comparable) to the minimum of all values previously added to the instance using add. If no values have been added it should return null.
max takes no arguments and returns a reference (as a Comparable) to the maximum of all values previously added to the instance using add. If no values have been added it should return null.

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 to add.

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 Control-Enter to run Example.main above

Let’s find all nodes in the tree and add them to a list.

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.

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 the code above

import java.util.List;
import java.util.ArrayList;
import java.util.Random;

public class BinaryTree {
  private static Random random = new Random();
  private class Node {
    private Object value;
    private Node right;
    private Node left;
    Node(Object setValue) {
      value = setValue;
    }
  }
  private Node root;
  BinaryTree(Object[] values) {
    for (Object value : values) {
      add(root, value);
    }
  }
  public void add(Object value) {
    add(root, value);
  }
  private void add(Node current, Object value) {
    if (current == null) {
      root = new Node(value);
    } else if (current.right == null) {
      current.right = new Node(value);
    } else if (current.left == null) {
      current.left = new Node(value);
    } else if (random.nextBoolean()) {
      add(current.right, value);
    } else {
      add(current.left, value);
    }
  }
  public String toString() {
    return toString(root);
  }
  private String toString(Node current) {
    if (current == null) {
      return "";
    }
    return "[" + current.value.toString() + "]" +
      toString(current.right) + toString(current.left);
  }
  public List allValues() {
  }
}

public class Example {
  public static void main(String[] unused) {
    BinaryTree binaryTree = new BinaryTree(new Integer[] { 1, 2, 3, 4 });
    System.out.println(binaryTree.allValues());
  }
}

> Click or hit Control-Enter to run Example.main above

Every sub(blank) of a (blank) is, itself, a (blank).

Tree
(Contiguous) List
(Contiguous) Array

Just use a loop.

public class SimpleLinkedList {
  class Item {
    Object value;
    Item next;
    Item(Object setValue, Item setNext) {
      value = setValue;
      next = setNext;
    }
  }
  public Item start;

public SimpleLinkedList(Object[] array) {
    for (int i = array.length - 1; i >= 0; i--) {
      this.add(0, array[i]);
    }
  }
  public void add(int index, Object toAdd) {
    if (index == 0) {
      start = new Item(toAdd, start);
    }
  }
  public void reverse() {
    if (start == null) {
      return;
    }
    Item previous = null;
    Item current = start;
    while (current != null) {
      // Save next since we are about to overwrite it
      Item next = current.next;
      current.next = previous;
      previous = current;
      current = next;
    }
    start = previous;
    return;
  }
  public String toString() {
    String toReturn = "";
    for (Item current = start; current != null; current = current.next) {
      toReturn += current.value;
    }
    return toReturn;
  }
}
public class Example {
  public static void main(String[] unused) {
    SimpleLinkedList simpleList = new SimpleLinkedList(new Integer[] { 1, 2, 5 });
    System.out.println(simpleList);
    simpleList.reverse();
    System.out.println(simpleList);
  }
}

> Click or hit Control-Enter to run Example.main above

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

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 bring together several of the things that we have discussed recently:

Imperative programming
Big-O algorithm runtime analysis
Recursion

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

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.

And we won’t discuss them all…

Insertion sort (today)
Selection sort (lab)
Merge sort (lecture)
Heapsort
Quicksort (lecture)
Bubble sort (lab)
And even new ones, like Timsort (circa 2002)

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.

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?

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

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

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

3	4	5	7	8	11	6	-1

3

4

5

7

8

11

6

-1

Let’s look at one step in more detail

						6
3	4	5	7	8	11		-1

Let’s look at one step in more detail

					6
3	4	5	7	8	11		-1

Let’s look at one step in more detail

					6
3	4	5	7	8		11	-1

Let’s look at one step in more detail

					6
3	4	5	7		8	11	-1

Let’s look at one step in more detail

				6
3	4	5	7		8	11	-1

Let’s look at one step in more detail

				6
3	4	5		7	8	11	-1

Let’s look at one step in more detail

			6
3	4	5		7	8	11	-1

Let’s look at one step in more detail

3	4	5	6	7	8	11	-1

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

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)

Measure	Best Case	Worst Case	Average Case
Time	O(n)	O(n^2)	O(n^2)
Space	O(1)	O(1)	O(1)

Measure

Best Case

Worst Case

Average Case

Time

O(n)

O(n^2)

Space

O(1)

Optimal sorting algorithms should be O(n log n) in the worst case and close to O(n) in the best case.

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.

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

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

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

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

E1 Review: MinMax

E1 Review: MinMax

Questions About Midterm 1?

Recursive Tree Traversal

What’s Our (Recursive) Algorithm?

Recursive Tree Traversal

Java ArrayLists

Other Recursive Data Structures

But Don’t Recurse on Lists

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Sorting Algorithms

Sorting Matters

In Memory of Jim Gray, Turing Award Winner

There Are Many Sorting Algorithms

Sorting Basics

Analyzing Sorting Algorithms

Insertion Sort: Overview

Insertion Sort: Overview

Insertion Sort: Insertion

Insertion Sort: A Single Step

Insertion Sort: A Single Step

Insertion Sort: A Single Step

Insertion Sort: A Single Step

Insertion Sort: A Single Step

Insertion Sort: A Single Step

Insertion Sort: A Single Step

Insertion Sort: A Single Step

Insertion Sort: A Single Step

Insertion Sort Runtime

Insertion Sort Runtime

We Can Do Better

Announcements

E1 Review: `MinMax`

E1 Review: `MinMax`

Java `ArrayList`s

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

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