Algorithm Design Manual - Booknotes

Factors:
  • Increasing or decreasing order?
  • Sorting the key or entire record?
  • Equal keys. Now what?
  • Non-numerical data. Now what?
  • Heapsort

    A heap-labeled tree = a binary tree such that the key of each node "dominates" the keys of its children. You can store a binary tree in an array w/o pointers - space efficient, but missing nodes take up unused space.

    Mergesort

    Partition elements into two groups, sort each smaller problem recursively, then interleave two sorted lists to order the merged elements.

    Quicksort
    Distribution Sort

    Ex: sorting phone book by 1st letter of last name ==> 26 buckets. Repeat with 2nd letter of last name (smaller piles), etc. Done when each bucket contains a single name.

    Effective when distribution is roughly uniform, terrible when not.

    Binary Search & Related algos

    Fast algorithm for searching a sorted array of keys.