CSSE 230: Session Notes - Day 25

Topics

1. Quicksort
2. Evaluation of sorting algorithms
3. Recurrence relations

Outline

1. [15 min] Evaluation of sorting algorithms
2. [15 min] Quicksort
3. [5 min] Definition of recurrence relations
4. [30 min] Developing and solving a recurrence relations for
   • Worst case of linear search
   • Worst case of binary search
   • Worst case of merge sort
   • Best case of merge sort
   • Worst case of quick sort
   • Average case of quick sort (if time permits)
5. [5 min] Break
6. [balance of time] Work on pair project

Resources

• QuickSort code.
• Slides for recurrence relations
• Quicksort partition animation

Homework

1. Day 27, BC: Recurrence homework
   Day 27, BC: Graph analysis