CMU 15-110: Principles of Computing
Searching and Sorting

  1. Simulations
    • Searching
      See here for linear search and binary search.

    • Sorting
      See here for selection sort and merge sort.

  2. What You Need To Know
    1. How linear search works: check each item in order.
    2. How binary search works: for a sorted list, keep checking the middle item and eliminating half the remaining items on each check.
    3. What Big-Oh is. Basically, ignore constants and lower-order terms.
    4. Linear search through a list with n values is O(n).
    5. Binary search through a sorted list with n values is O(logn).
    6. logn is much, much smaller than n
    7. So binary search is much, much faster than linear search.

    8. When we say logn without a base, we mean base 2.
    9. 210 is about 1 thousand, 220 is about 1 million, 230 is about 1 billion.
    10. log(1 thousand) is about 10, log(1 million) is about 20, log(1 billion) is about 30.

    11. How selection sort works: keep selecting the largest remaining element and swapping it into place.
    12. How merge sort works: keep merging sorted sub-lists of size k into sorted sub-lists of size 2k (so, 1 into 2, then 2 into 4, and so on).
    13. Selection sort is O(n2). Prove this.
      • The first pass of selection sort takes n steps (n-1 compares and one swap).
      • The second pass takes (n-1) steps.
      • And so on.
      • So: total steps = n + (n-1) + ... + 2 + 1 = (n/2)(n+1)
      • So: total steps is O(n2).
    14. Merge sort is O(nlogn). Prove this.
      • The first pass takes 3n steps -- n compares, n copies down, n copies back up.
      • In fact, each pass takes 3n steps.
      • So the total steps is 3n * (# of passes).
      • There are logn number of passes (since the size of the sorted sublists doubles on each pass).
      • So the total steps is 3n * (logn).
      • So the total steps is O(nlogn).
    15. Since logn is much smaller than n, nlogn is much smaller than n2.
    16. So merge sort is much, much, much faster than selection sort.