Recursion and Sorting

"Can’t worry about what’s behind you, or what’s coming for you further up the road." At least, so says the Swedish duo First Aid Kit.

As an odd aside, the video for "Silver Lining" is the second I’ve watched recently that features a self-driving car—although, in both cases, it’s more of a metaphor than a technological statement. We’ll watch the second on Friday.

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

Base case: We’ve reached a node with no descendants. Return true if its value matches, zero otherwise.
Recursive step: Consider our right tree and left tree separately.
Combine results: Return true if either we or our right or left subtree contain the search value.

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);
      return;
    }
    if (random.nextBoolean()) {
      if (current.right == null) {
        current.right = new Node(value);
      } else {
        add(current.right, value);
      }
    } else {
      if (current.left == null) {
        current.left = new Node(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 boolean search(Object value) {
  }
}
public class Example {
  public static void main(String[] unused) {
    BinaryTree binaryTree = new BinaryTree(new Integer[] {1, 2, 3, 4});
		System.out.println(binaryTree.search(4));
  }
}

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

public class BinarySearchTree {
  private class Node {
    private Comparable value;
    private Node right;
    private Node left;
    Node(Comparable setValue) {
      value = setValue;
    }
  }
  private Node root;
  BinarySearchTree(Comparable[] values) {
    for (Comparable value : values) {
      add(root, value);
    }
  }
  public void add(Comparable value) {
    add(root, value);
  }
  private void add(Node current, Comparable value) {
    if (current == null) {
      root = new Node(value);
      return;
    }
    if (current.value.compareTo(value) >= 0) {
      if (current.right == null) {
        current.right = new Node(value);
      } else {
        add(current.right, value);
      }
    } else {
      if (current.left == null) {
        current.left = new Node(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 boolean search(Object value) {
  }
}
public class Example {
  public static void main(String[] unused) {
    BinarySearchTree binarySearchTree = new BinarySearchTree(new Integer[] {1, 2, 3, 4});
    System.out.println(binarySearchTree.search(3));
  }
}

> 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);
      return;
    }
    if (random.nextBoolean()) {
      if (current.right == null) {
        current.right = new Node(value);
      } else {
        add(current.right, value);
      }
    } else {
      if (current.left == null) {
        current.left = new Node(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

public class Item {
  public int value;
  public Item next;
  Item(int setValue, Item setNext) {
    value = setValue;
    next = setNext;
  }
}

public class Item {
  public int value;
  public Item next;
  Item(int setValue, Item setNext) {
    value = setValue;
    next = setNext;
  }
}

public class Item {
  public int value;
  public Item next;
  Item(int setValue, Item setNext) {
    value = setValue;
    next = setNext;
  }
}

public class Item {
  public int value;
  public Item next;
  Item(int setValue, Item setNext) {
    value = setValue;
    next = setNext;
  }
}

public class Item {
  public int value;
  public Item next;
  Item(int setValue, Item setNext) {
    value = setValue;
    next = setNext;
  }
}

Just like with trees, 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 the current item and the rest of the list.
What’s the smallest subproblem? A list with a single element.

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 (Friday)
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?

All of you will get a job. Not all of you will get a great 1 job.

Here’s a good strategy for not getting a good job:

Take CS classes.
Do the projects.
Get good grades.
Don’t do any side projects: focus on grades instead.

Show your passion for technology.

The CS 125 Final Project is intended to get you started doing that.

I have virtual office hours today from 4–5PM. Please come by and say hi!

Today’s Musical Selections

Recursive Tree Search

How Could We Make This Search More Efficient?

Recursive Tree Traversal

What’s Our (Recursive) Algorithm?

Recursive Tree Traversal

Java ArrayLists

Other Recursive Data Structures

List Recursion

List Recursion

List Recursion

List Recursion

List Recursion

List 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

Array Recursion

Questions About Recursion?

Sorting Algorithms

Sorting Matters

In Memory of Jim Gray, Turing Award Winner

There Are Many Sorting Algorithms

Sorting Basics

Analyzing Sorting Algorithms

CS 125 Final Project

How to Not Get a Great CS Job

How to Get a Great CS Job

Example Fall 2019 Final Projects

Announcements

Java `ArrayList`s