CSSE 230: Session Notes - Day 22

Topics

1. Lower bound on comparison based sorting
2. Linear time sorting
3. Constant time sorting

Outline

1. [5 min] Contact before work
2. [10 min] The game of 20 questions
3. [20 min] Proof of lower bound on comparison based sorting.
4. [20 min] RadixSort and analysis of it.
5. [5 min] Break
6. [10 min] Constant time sorting
7. [Balance of time] work on team project

Resources

• Sorting by classificationcode shown in class
• Proof of lower bound of comparison based sorting
• Radix sort animation
• RadixSort for strings.
• A video narrating the lower bound of comparison based sorting proof
• A video narrating linear sorting
• A video narrating constant time sorting