4. YSC2229 Lecture Notes, Week 04

• 4.1. OCaml REPL and Multiple Files
• 4.2. Quicksort and Its Variations
  • 4.2.1. Partitioning an array
  • 4.2.2. Partitioning in action
  • 4.2.3. Sorting via partitioning
• 4.3. Complexity of Divide-and-Conquer Algorithms
  • 4.3.1. Changing variable in recurrence relations
  • 4.3.2. Complexity of Merge Sort
  • 4.3.3. Complexity of Quicksort
  • 4.3.4. The Master Theorem
• 4.4. Generalising Comparison-Based Sorting
  • 4.4.1. Comparator as a parameter
  • 4.4.2. A functor for sorting
• 4.5. Best-Worst Case for Comparison-Based Sorting
• 4.6. Sorting in Linear Time
  • 4.6.1. Simple Bucket Sort
  • 4.6.2. Enhanced Bucket Sort
  • 4.6.3. Stability of sorting
  • 4.6.4. Radix Sort
• 4.7. Exercises
  • 4.7.1. Mandatory exercises
  • 4.7.2. Recommended exercises
  • 4.7.3. Exercise 1
  • 4.7.4. Exercise 2
  • 4.7.5. Exercise 3
  • 4.7.6. Exercise 4
  • 4.7.7. Exercise 5
  • 4.7.8. Exercise 6
  • 4.7.9. Exercise 7
  • 4.7.10. Exercise 8
  • 4.7.11. Exercise 9

Supplementary materials

• Code from Week 4: quick sort, comparison-based sorrting and linear-time sorting.