15-112: Fundamentals of Programming and Computer Science
Class Notes: Efficiency
Use the following notes, except:
- Add these topics:
- Input Size
- For list L: n = # of elements in the list == len(L)
- For integer n: we generally use n in 112, but technically should use size(n) == # of bits to represent n = log2(n)
- Sorting Links
- Wikipedia page on Sorting
- David Eck's xSortLab applet (or you might try this jar file )
- Our sorting sample code (You need to be able to write all of this from scratch!)
- Excellent sorting animation website
- Sorting algorithm animation video (15 algorithms in 6 minutes)
- Even more sorting algorithm animations
- BubbleSort
You are responsible for writing (from scratch), understanding, and analyzing SelectionSort, BubbleSort, and MergeSort, and any reasonable variations of those. See here.
- Sort Properties
- Time Complexity (best, average, and worst cases). Note: in 112, we mostly prove best and worst cases.
- Space Complexity (best, average, and worse cases).
- In-Place (Uses O(1) space; ie, constant-sized memory (not counting the input))
- Stable (maintains relative order of equal values)
- Adaptive (recognizes pre-sorted lists)
- Comparison-Based. Note: best-possible comparison-based algorithm is O(nlogn)
- Serial or Parallel. Note: we only consider serial sorts in 112.
- Implementation Details
- Iterative vs Recursive
- Destructive vs Nondestructive
- Input Size
- Omit these topics:
- Omit example #4 (isPrime(nthHappyNumber(n)))
- Omit example #6 (Sum of Prime Factors)
Taking everything above into account, use these notes.