Skip to content

Sorting and Search

  • Comparison sorts: bubble sort, insertion sort, merge sort, quicksort (pivot strategies, Hoare vs Lomuto partition), heapsort
  • Lower bound for comparison sorting: O(n log n) via decision trees
  • Non-comparison sorts: counting sort, radix sort, bucket sort
  • Binary search: standard, lower/upper bound, search on answer (monotonic functions)
  • Divide and conquer: master theorem, merge sort analysis, closest pair of points
  • Greedy algorithms: activity selection, Huffman coding, interval scheduling
  • Dynamic programming: overlapping subproblems, optimal substructure, memoisation vs tabulation, classic problems (knapsack, LCS, edit distance, coin change)
  • Backtracking: N-queens, Sudoku, constraint satisfaction