CPS 6, Ramm - Spring 2000 - 4/10/00, #32
11. Sorting, Templates, and Generic Programming
- Analysis of Quicksort (average case)
- Look at sort in terms of levels (depth of recursion)
- How much work at each level?
- How deep do we go?
- Overall Complexity
- Worst Case (covered by Duvall)
- O (big-Oh) Notation to Describe Complexity
- Describes asymptotic behavior
- Selection Sort: O(N*N) or O(N^2)
- Quick Sort: O(________)
- Other Sophisticated, Fast Sorts
- Mostly to expose you to the names
- Merge Sort
- Heap Sort
- Binary Tree Sort
- All O(________)
- Other Simple Sorts
- Insertion Sort
- Almost used in wordlist problem
- Develop Algorithm
- Bubble Sort (XXX)
- All O(________)
- Sorting Complex Objects
- May need to sort structs
- What do we compare?
- Use Operator Overloading
- What Are Some Other big-Ohs?
- Can O(...) be so Large as to make answer Impossible?
- Towers of Hanoi
- Computer Chess