1 of 6

Sorting, Searching, �and big O Notation

2 of 6

Sorting

  • Sorter.java We start with Sorter.java. It is a utility class. You don’t have to understand its contents. We’re going to use it to run the other Sorters
  • BubbleSorter.java One of the simplest sorters.
  • SelectionSorter.java Another simple sorter.
    • Run: java Sorter SelectionSorter 3000 100
    • Run: java Sorter SelectionSorter 6000 25
    • Twice as big runs 4 times as long, proportional to N squared

3 of 6

Can we do better?

  • MergeSorter.java
    • The code completes in a time proportional to N Log(N)
    • Run: java Sorter MergeSorter 60000 100
    • Uses Recursion
    • Stable
  • QuickSorter2.java
    • Like MergeSorter, time is proportional to N Log(N)
    • Run: java Sorter QuickSorter 60000 100
    • Uses Recursion
    • Uses a random number!
    • Not stable

4 of 6

Big O Notation

  • O(N) means takes order N time. That could be 2*N seconds, or 3*N+1 seconds. The point is, for very large N it grows as N.
  • O(2 N) is always wrong. There should be no coefficient.
  • O(N+1) is always wrong. The N dominates the 1 for large N.
  • Technically, Big O is an upper bound.
    • We will always assume it is a tight upper bound.
  • Technically, Big O for quicksort is O(N^2).
    • In this course, we will always say quicksort is O(N log(N)) because that is the observed behavior.
  • An important tool in computer science!

5 of 6

What if we don’t want to sort ints?

  • Cmp.java
  • MergeSorterO.java
    • Why do we compute the midpoint using lo + (hi-lo)/2 instead of (lo+hi)/2? Roundoff error. To understand this, take a look at Mid.java
  • QuickSorterO.java
    • Does not use Sorter.java
    • Can sort Strings as well as ints.
    • Can sort anything that is Comparable.
    • What is Comparable?
  • Rocket.java
    • Implements Comparable
    • Sorts based on more than one thing

6 of 6

Searching

  • Searcher.java Like Sorter.java, you don’t need to know how it works
    • Like Sorter, first arg is class name, 2nd arg is array size, third arg is num of tries
  • LinearSearcher.java
    • Time complexity O(N)
    • As simple as it gets
    • Run: java Searcher LinearSearcher 1000000 100
  • BinarySearcher.java
    • Requires a sorted array
    • Time complexity O(Log(N))
    • Run: java Searcher BinarySearcher 100000000 100