Algorithms

An algorithm is a list of steps that solves a problem: given some input, it does a fixed series of things and ends with an output. A recipe is one: the input is flour, eggs and milk, the steps say exactly what to do and in which order, and the output is pancakes. A computer program is an algorithm written in a language a computer can run. In this course that language is C++.

Algorithm

A finite list of precise steps that turns an input into an output.

Input

What the algorithm is given to work on: a list, a number, a word.

Output

What it gives back at the end: the answer.

Step

One small action with no room for guessing, such as “compare these two numbers”.

Looking up a word in a paper dictionary, sorting a hand of playing cards, or finding the tallest person in a queue are all algorithms. You do them without thinking, but each can be written as steps. The hard part, and the whole point of this course, is writing the steps so precisely that someone with no common sense, a computer, gets the right answer every time.

Two things matter before anything else. Correctness: for every valid input, the output is the right answer, not just for the examples you tried. Termination: it always stops. A recipe that says “stir until it looks right” may never end; one that says “stir for 2 minutes” always does.

Here is the problem this module solves: given a list of scores, find the largest. In words: look at the first score and remember it. Then look at each of the others; whenever one is bigger than the one you remember, remember that one instead. At the end, the one you remember is the answer. Pseudocode writes the same steps in a short, code-like way that is not any real language.

1largest(scores):2  if scores is empty: answer "nothing"3  best ← the first score4  for each other score s:5    if s > best:6      best ← s7  answer best

Each line of pseudocode becomes a line or two of C++. The scores come in a std::vector<int>, passed as const& so the function reads the caller’s vector without copying it. “Nothing” needs a type that can be empty: std::optional<int> holds either an int or nothing, written std::nullopt. The return type says so, and the caller must deal with an empty list.

1#include <iostream>2#include <optional>3#include <vector>4
5std::optional<int> largest(const std::vector<int>& scores) {6  if (scores.empty()) return std::nullopt;7  int best = scores[0];8  for (size_t i = 1; i < scores.size(); i++) {9    if (scores[i] > best) {10      best = scores[i];11    }12  }13  return best;14}15
16int main() {17  std::cout << *largest({4, 9, 2}) << "\n";      // 918  std::cout << largest({}).has_value() << "\n";  // 019}

1std::optional<int> smallest(const std::vector<int>& prices) {2  if (prices.empty()) return ;3  int best = prices[0];4  for (size_t i = 1; i < prices.; i++) {5    if (prices[i]  best) best = prices[i];6  }7  return best;8}

Tracing means running the steps yourself, on paper, and writing down every variable after every step. It is the surest way to understand an algorithm, and to find out why one is wrong. Here is largest on {4, 9, 2, 11}.

Write it yourself. Think about the edge cases first: the inputs at the edges of what is allowed, like an empty list, a list of one, or all negative numbers.

1#include <optional>2#include <vector>3
4std::optional<int> largest(const std::vector<int>& scores) {5  int best = 0;6  // TODO: look at every score and keep the biggest7  return best;8}

Real data is usually records. A struct groups named fields into one type; to find the cheapest book, compare a field, price, but remember the whole book. And decide what happens on a tie: here, the first book found wins, so the comparison is a strict <.

1#include <optional>2#include <string>3#include <vector>4
5struct Book {6  std::string title;7  int price;8};9
10std::optional<Book> cheapest(const std::vector<Book>& books) {11  return std::nullopt;  // TODO12}

1#include <iostream>2#include <vector>3
4int comparisons = 0;5
6int largest(const std::vector<int>& scores) {7  int best = scores[0];8  for (size_t i = 1; i < scores.size(); i++) {9    comparisons++;10    if (scores[i] > best) best = scores[i];11  }12  return best;13}14
15int main() {16  for (int n : {10, 100, 1000}) {17    std::vector<int> scores(n);18    for (int i = 0; i < n; i++) scores[i] = (i * 37) % 101;19    comparisons = 0;20    largest(scores);21    std::cout << n << " scores: " << comparisons22              << " comparisons\n";23  }24}

• An algorithm is a finite list of precise steps from an input to an output.
• It must be correct for every valid input and must terminate.
• Write it in words, then pseudocode, then code; each step maps to a line or two.
• Trace it by hand on a small input to see what every variable does.
• Test the edge cases: empty, one element, all negative, ties.
• std::optional says “maybe no answer” in the type; check it before reading scores[0].
• Finding the largest: remember the best so far, compare each one, answer at the end.

Finding the cheapest of 10 prices is instant; of 10 million, it takes a moment. So “how fast is it?” has no single answer: it depends on the input size, written n (the number of prices, songs, books). Seconds also depend on the computer, so instead we count operations, the small steps like a comparison or an addition, and ask how that count grows as n grows.

Input size (n)

How big the input is: usually the number of elements in a list.

Operation

One basic step that takes a fixed time: compare, add, read an element.

Running time

How many operations an algorithm does, as a function of n.

Growth

How fast that count rises as n gets bigger. It is what we compare.

To count, look at what runs once and what runs once per element. Adding up a playlist’s song lengths sets a total once, then does one addition per song, then returns once. For n songs that is about n + 2 operations.

1int totalLength(const std::vector<int>& songs) {2  int total = 0;              // once3  for (int s : songs) {4    total += s;               // n times5  }6  return total;               // once7}

1int n = 4;2for (int i = 0; i < n; i++) {3  for (int j = 0; j < n; j++) {4    std::cout << i << " " << j << "\n";5  }6}

Big O is a short way to write how the count grows. Two rules: keep only the fastest-growing term, and drop constant factors. So n + 2 is O(n), 3n is O(n), and 5n² + 100n + 7 is O(n²): when n is a million, the n² part is so much bigger that the rest does not matter. You read O(n) as “order n” or “linear”.

A few shapes come up again and again. log n (the logarithm) is how many times you can halve n before you reach 1: about 10 for a thousand, 20 for a million. It grows so slowly it is almost constant. 2ⁿ doubles with every extra element, and is hopeless past about 40.

• O(1): reading list[5], or the front of a queue.
• O(log n): finding a word in a dictionary by halving (module 4).
• O(n): looking at every price once.
• O(n log n): good sorting, like merge sort (module 7).
• O(n²): comparing every pair of songs.
• O(2ⁿ): trying every possible playlist made from n songs.

Most of the time you can read Big O straight from the shape of the code. One loop over the input is O(n). A loop inside a loop, both over the input, is O(n²). Two loops one after the other are O(n) + O(n), still O(n). A loop that halves what is left each time is O(log n).

1int first = list[0];                     // O()2for (int x : list) total += x;           // O()3for (int a : list) {4  for (int b : list) total += a * b;     // O()5}6for (size_t k = list.size(); k > 1; k = k / 2) {7  total += k;                            // O()8}

1bool hasDuplicate(const std::vector<std::string>& items) {2  for (size_t i = 0; i < items.size(); i++) {3    for (size_t j = i + 1; j < items.size(); j++) {4      if (items[i] == items[j]) return true;5    }6  }7  return false;8}

Code can count its own work: a global variable, declared outside every function, is shared by all of them. Here same(a, b) adds 1 to comparisons each time it is called, so after a run the tests can check not just the answer, but how much work it took.

1#include <string>2#include <vector>3
4int comparisons = 0;5bool same(const std::string& a, const std::string& b) {6  comparisons++;7  return a == b;8}9
10bool hasDuplicate(const std::vector<std::string>& items) {11  for (size_t i = 0; i < items.size(); i++) {12    for (size_t j = 0; j < items.size(); j++) {13      if (same(items[i], items[j])) return true;14    }15  }16  return false;17}

1int halvings(int n) {2  int steps = 0;3  // TODO: halve n until it is 0, counting each step4  return steps;5}

Space complexity is how much extra memory an algorithm needs as n grows, beyond the input itself. A few variables are O(1) space. Building a new list as big as the input is O(n) space. Often you can trade one for the other: use more memory to save time, or less memory at the cost of time.

std::vector<int> reversed(    const std::vector<int>& list) {  std::vector<int> out;  for (size_t i = list.size(); i > 0; i--) {    out.push_back(list[i - 1]);  }  return out;}

void reverseInPlace(std::vector<int>& list) {  if (list.empty()) return;  size_t i = 0;  size_t j = list.size() - 1;  while (i < j) {    int t = list[i];    list[i] = list[j];    list[j] = t;    i++;    j--;  }}

The same algorithm can do very different amounts of work on inputs of the same size. Looking for a song in a playlist of n songs takes 1 comparison if it is first (the best case) and n if it is last or missing (the worst case). The average case is in between. When people give one Big O without saying which, they mean the worst case: it is a promise that holds for every input.

std::chrono::steady_clock::now() (in <chrono>) reads a clock that only ever moves forward. Read it before and after, and subtract. Here an O(n²) duplicate check races an O(n) one that remembers what it has seen in a std::unordered_set (a collection that answers “have I seen this?” in about one step; module 10 explains it).

1#include <chrono>2#include <iostream>3#include <unordered_set>4#include <vector>5
6bool slow(const std::vector<int>& items) {7  for (size_t i = 0; i < items.size(); i++)8    for (size_t j = i + 1; j < items.size(); j++)9      if (items[i] == items[j]) return true;10  return false;11}12
13bool fast(const std::vector<int>& items) {14  std::unordered_set<int> seen;15  for (int x : items) {16    if (seen.contains(x)) return true;17    seen.insert(x);18  }19  return false;20}21
22int main() {23  std::vector<int> items;24  for (int i = 0; i < 10000; i++) items.push_back(i);25  auto t0 = std::chrono::steady_clock::now();26  bool a = slow(items);27  auto t1 = std::chrono::steady_clock::now();28  bool b = fast(items);29  auto t2 = std::chrono::steady_clock::now();30  std::chrono::duration<double, std::milli> s = t1 - t0, f = t2 - t1;31  std::cout << "slow " << a << ", " << s.count() << " ms\n";32  std::cout << "fast " << b << ", " << f.count() << " ms\n";33}

• Count operations as a function of the input size n, rather than seconds.
• Big O keeps the fastest-growing term and drops constants: 3n + 2 is O(n).
• O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).
• One loop is O(n), nested loops O(n²), halving O(log n).
• Space complexity counts the extra memory: a copy is O(n), a few variables O(1).
• Without a qualifier, Big O means the worst case.

A friend’s bookshelf is in no order and you want Dune. There is only one way: look at the first book, then the next, and so on, until you find it or run out of shelf. That is linear search: check each element in turn. It works on any list, sorted or not, and it is what the standard library’s std::find does inside.

Search

Finding whether a value is in a collection, and usually where.

Target

The value you are looking for.

Linear search

Checking each element in order, from the first, until the target is found.

Sentinel value

A special answer that means “not found”, such as -1 for an index, std::nullopt for a value, or end() for a position.

Walk the indexes from 0, compare each element with the target, and return the index the moment they match. If the loop finishes, every element was checked and none matched, so return the sentinel -1. The index is an int, which can be negative; std::ssize(list) gives the size as a signed number too, so the two compare cleanly.

1int linearSearch(const std::vector<std::string>& list,2                 const std::string& target) {3  for (int i = 0; i < std::ssize(list); i++) {4    if (list[i] == target) {5      return i;6    }7  }8  return -1;9}10
11int main() {12  std::vector<std::string> shelf = {"Emma", "Kim", "Dune",13                                    "Ulysses"};14  std::cout << linearSearch(shelf, "Dune") << "\n";    // 215  std::cout << linearSearch(shelf, "Hamlet") << "\n";  // -116}

<algorithm> has searches built in. They all walk from the start, so they are all O(n); they differ in what you give them and what they give back. Most give back an iterator: a position in the container. *it reads the element there, it - v.begin() turns it into an index, and v.end(), the position one past the last element, means “not found”.

1std::vector<int> v = {4, 9, 2};2auto it = std::ranges::find(v, 7);3std::cout << (it == v.end()) << " " << (it - v.begin());

Write it without std::find, so you know exactly what it does. Then a twist: search from the other end.

1#include <vector>2
3int linearSearch(const std::vector<int>& prices, int target) {4  // TODO: check each price in turn5  return -1;6}

1#include <string>2#include <vector>3
4int lastIndex(const std::vector<std::string>& songs,5              const std::string& title) {6  for (int i = 0; i < std::ssize(songs); i++) {7    if (songs[i] == title) return i;8  }9  return -1;10}

Often you don’t know the exact value, only what it must be like: the first price under 10, the first song longer than five minutes. Pass the condition in as a function, called a predicate: it takes one element and answers true or false. A lambda writes one on the spot: [](int s) { return s > 300; } is a nameless function of an int. This is how find_if works.

1std::vector<int> lengths = {215, 187, 342, 401};2auto isLong = [](int s) { return s  300; };3auto it = std::ranges::(lengths, isLong);4std::cout << *it;   // prints 

1#include <optional>2#include <vector>3
4template <typename Test>5std::optional<int> findFirst(const std::vector<int>& prices,6                             Test test) {7  std::vector<int> passing;8  for (int p : prices) {9    if (test(p)) passing.push_back(p);10  }11  if (passing.empty()) return std::nullopt;12  return passing[0];13}

An early exit leaves the loop the moment the answer is known, with return (leave the function) or break (leave just the loop). It does not change the worst case, a missing target still costs n comparisons, but it makes the best and average cases much cheaper. Forgetting it is a common bug, and not only for speed.

1#include <iostream>2#include <vector>3
4int steps = 0;5
6int search(const std::vector<int>& list, int target) {7  steps = 0;8  for (int i = 0; i < std::ssize(list); i++) {9    steps++;10    if (list[i] == target) return i;11  }12  return -1;13}14
15int main() {16  std::vector<int> list;17  for (int i = 0; i < 10000; i++) list.push_back(i * 2);18  for (int target : {4, 10000, 7}) {19    int index = search(list, target);20    std::cout << target << ": index " << index << ", " << steps21              << " steps\n";22  }23}

Every search must decide what to answer when there is nothing to find, and every caller must check for it. A sneaky trap: testing an index with if (index). In C++, if on an int means “is it not 0”, so a real find at index 0 looks like a miss, and the sentinel -1 looks like a find.

1std::vector<int> fines = {0, 3, 5};2int spot = linearSearch(fines, 0);3if (spot) std::cout << "found a free one";4else std::cout << "none free";

With a list of structs you usually search on one field: a book by its ISBN, a member by their email. The condition can combine fields, too: the first book by an author that is not on loan.

1#include <optional>2#include <string>3#include <vector>4
5struct Book {6  std::string title;7  std::string author;8  bool onLoan;9};10
11std::optional<Book> firstAvailable(const std::vector<Book>& books,12                                   const std::string& author) {13  for (const Book& b : books) {14    if (b.author == author) return b;15  }16  return std::nullopt;17}

• Linear search checks each element in turn: O(n), and it works on any list.
• Return the first match at once; return a sentinel (-1, std::nullopt) only after the loop.
• std::ranges::find looks for a value with ==; find_if and any_of take a predicate.
• A failed find gives end(), one past the last element: compare with it before reading *it.
• Counting down needs a signed index: a size_t never goes below 0.
• Check “not found” against the sentinel, not with if (index): index 0 is a real find.

Nobody looks up “otter” in a dictionary by reading from page one. You open it near the middle, see “monkey”, and know “otter” is in the second half: half the book is ruled out in one look. Open the middle of what is left, and again. Binary search does exactly this, on a list that is sorted: in order, smallest first. It is the reason sorted data is worth so much.

Sorted

In order, each element no smaller than the one before.

Binary search

Searching a sorted list by comparing with its middle and throwing away the half that cannot hold the target.

O(log n)

The number of times n can be halved: about 20 for a million.

Keep two markers: lo, the first index that could still hold the target, and hi, the last. Look at the element halfway between, mid. If it is the target, done. If it is smaller, the target must be to its right, so move lo past it. If bigger, move hi before it. When lo passes hi, nothing is left: not found. Here is a search for 24 in [3, 8, 12, 19, 24, 31, 40].

The last test runs 100,000 searches in a sorted list of a million numbers. A linear scan would need billions of steps and runs out of the 2 seconds a test may take; binary search needs about 2 million.

1#include <vector>2
3int binarySearch(const std::vector<int>& sorted, int target) {4  int lo = 0;5  int hi = std::ssize(sorted) - 1;6  // TODO: halve the range until it is found or empty7  return -1;8}

Binary search is short and famously easy to get wrong. An off-by-one error is being one away from the right index: a < that should be <=, a mid that should be mid + 1. The rule that keeps it straight: decide what lo and hi mean (here, both are indexes that could still hold the target) and make every line keep that true.

Often you want not “is it there?” but “where does it belong?”: the insertion point, the first index whose element is at least the target. This is called the lower bound. It answers how many items are smaller, where to insert to keep the list sorted, and finds the first of several equal values. Here hi starts at the size, one past the end, because the answer can be “after everything”.

1int lowerBound(const std::vector<int>& sorted, int x) {2  int lo = 0;3  int hi = std::ssize(sorted);4  while (lo < hi) {5    int mid = lo + (hi - lo) / 2;6    if (sorted[mid] < x) lo = mid + 1;7    else hi = mid;8  }9  return lo;10}11
12int main() {13  std::vector<int> v = {10, 20, 20, 30};14  std::cout << lowerBound(v, 20) << "\n";  // 115  std::cout << lowerBound(v, 25) << "\n";  // 316  std::cout << lowerBound(v, 99) << "\n";  // 417}

1std::vector<int> prices = {4, 9, 15, 22};2int at = lowerBound(prices, );           // 23prices.(prices.begin() + at, 12);4// prices is now {4, 9, , 15, 22}

A variation: the first index whose price is more than the budget. Every price before it is affordable, so that index is the count. Only one comparison changes from lowerBound.

1#include <vector>2
3int countAffordable(const std::vector<int>& sorted, int budget) {4  int lo = 0;5  int hi = std::ssize(sorted);6  // TODO: find the first index whose price is over budget7  return 0;8}

Binary search works on anything where the answer to a yes/no question flips once: “no, no, no, yes, yes”. A courier must deliver parcels in order, one van load per day, in at most days days. Is a van of capacity C big enough? If C works, any bigger van works too. So binary search the capacities for the smallest that works, between the heaviest parcel (anything less cannot carry it) and the total (one trip).

1#include <algorithm>2#include <vector>3
4int trips(const std::vector<int>& weights, int cap) {5  int count = 1, load = 0;6  for (int w : weights) {7    if (load + w > cap) {8      count++;9      load = 0;10    }11    load += w;12  }13  return count;14}15
16int smallestCapacity(const std::vector<int>& weights, int days) {17  int lo = 0, hi = 0;  // the heaviest parcel, the total18  for (int w : weights) lo = std::max(lo, w), hi += w;19  // TODO: binary search for the smallest cap that works20  return hi;21}

<algorithm> has binary search built in, for any sorted range. Like find, most give back an iterator, a position; subtract v.begin() for the index. They only promise a right answer when the range really is sorted: they cannot check it without reading everything, which would undo the point.

1#include <algorithm>2#include <iostream>3#include <vector>4
5int main() {6  for (int n : {100, 10'000, 1'000'000}) {7    std::vector<int> list(n);8    for (int i = 0; i < n; i++) list[i] = i;9    int x = n - 1;10
11    int linear = 0;12    for (int item : list) {13      linear++;14      if (item == x) break;15    }16
17    int binary = 0;18    auto less = [&binary](int a, int b) { binary++; return a < b; };19    auto it = std::ranges::lower_bound(list, x, less);20
21    std::cout << n << ": linear " << linear << ", lower_bound "22              << binary << ", found at " << it - list.begin() << "\n";23  }24}

• Binary search needs a sorted list, and halves the range each round: O(log n).
• Keep lo and hi meaning one thing; move them past mid with mid + 1 and mid - 1.
• Every round must shrink the range, or the loop never ends.
• Lower bound: the first index whose element is at least x, which is also its insertion point.
• The library has them: std::ranges::lower_bound, upper_bound, binary_search, equal_range.
• Test the first, last and missing elements, an empty list and one element: off-by-one errors hide there.
• Binary search on the answer: when “is C enough?” flips once, search for the smallest C that is.

Sorting means putting items in order: prices from low to high, names from A to Z, scores from best to worst. People sort to read a list more easily, and algorithms sort to make later work fast. In a sorted list, the smallest item is first, equal items sit next to each other, and binary search (the previous module) can find anything in a few steps.

Ascending

From smallest to largest: 1, 2, 3, or A to Z.

Descending

From largest to smallest: 3, 2, 1, or Z to A.

In place

Sorting by moving items around inside the same vector, with no second copy.

Swap

Exchanging two items’ positions: std::swap(a, b).

<algorithm> has std::ranges::sort(v) (the older spelling is std::sort(v.begin(), v.end())). It changes the vector you give it, and, without instructions, it orders items with <. For numbers that is what you expect. For std::string, < compares character by character, by each character’s code: every capital letter comes before every small one, and the text “10” comes before “9”, because the character 1 comes before 9.

1std::vector<std::string> names = {"Kim", "ada", "Emma"};2std::ranges::sort(names);   // {"Emma", "Kim", "ada"}: capitals first3
4std::vector<int> prices = {10, 9, 1, 100};5std::ranges::sort(prices);  // {1, 9, 10, 100}: numbers as numbers

1std::vector<std::string> scores = {"25", "3", "100", "42"};2std::ranges::sort(scores);

A comparator is a function (a, b) that returns true when a must come before b, and false otherwise, equal items included. It is usually a lambda, a function written on the spot. std::greater<>() is a ready-made one that uses >, for descending order. A comparator that reads one field is so common that C++20 has a short form, a projection: std::ranges::sort(books, {}, &Book::price) sorts by price with the default <.

1std::vector<int> prices = {10, 9, 1, 100};2std::ranges::sort(prices, std::greater<>());  // {100, 10, 9, 1}3
4struct Book {5  std::string title;6  int price;7};8std::vector<Book> books = {{"Kim", 7}, {"Emma", 5}};9std::ranges::sort(books, [](const Book& a, const Book& b) {10  return a.price < b.price;                    // Emma, Kim11});12std::vector<Book> copy = books;   // a copy, to sort separately13std::ranges::sort(copy, {}, &Book::title);

1std::ranges::sort(books, [](const Book& a, const Book& b) {2  if (a.price  b.price) return a.price  b.price;3  return a.title  b.title;4});

To see what sort does inside, write one. The simplest is bubble sort: walk along the list comparing each pair of neighbours, and swap them if they are in the wrong order. After one pass the largest item has “bubbled” to the end. Repeat, each pass stopping one place earlier, until the whole list is sorted.

1void bubbleSort(std::vector<int>& nums) {2  for (int end = std::ssize(nums) - 1; end > 0; end--) {3    for (int i = 0; i < end; i++) {4      if (nums[i] > nums[i + 1]) {5        std::swap(nums[i], nums[i + 1]);6      }7    }8  }9}10
11int main() {12  std::vector<int> v = {5, 1, 4, 2};13  bubbleSort(v);  // v is now {1, 2, 4, 5}14}

Selection sort is how many people sort a handful of exam papers by mark: find the lowest mark, put it first; find the lowest of the rest, put it second; and so on. Each round is the “find the smallest” algorithm from the first module, run on what is left. It does at most one swap per round, which helps when moving an item is expensive.

1void selectionSort(std::vector<int>& nums) {2  for (int i = 0; i + 1 < std::ssize(nums); i++) {3    int min = i;4    for (int j = i + 1; j < std::ssize(nums); j++) {5      if (nums[j] < nums[min]) min = j;6    }7    std::swap(nums[i], nums[min]);8  }9}

Picking up playing cards one at a time, you slide each new card left past the bigger ones until it sits in place. The cards in your hand are always sorted. That is insertion sort: the left part of the vector is a sorted hand, and each next item is inserted into it by shifting bigger items one place right.

1void insertionSort(std::vector<int>& nums) {2  for (int i = 1; i < std::ssize(nums); i++) {3    int card = nums[i];4    int j = i - 1;5    while (j >= 0 && nums[j] > card) {6      nums[j + 1] = nums[j];7      j--;8    }9    nums[j + 1] = card;10  }11}

A sort is stable if items that compare as equal stay in the order they were in. It matters when you sort by one thing after another: sort orders by time, then sort them stably by customer, and each customer’s orders are still in time order. Bubble and insertion sort are stable, because they only move an item past a strictly bigger one. Selection sort is not: its long-distance swap can jump an item over its equal.

All three use a loop inside a loop. For a list of n items, the outer loop runs about n times and the inner one up to n times, so in the worst case they take about n² steps: O(n²), quadratic. Doubling the list makes them four times slower. Insertion sort has a best case, though: on a list that is already nearly sorted, each card moves only a little, and the whole sort is close to n steps.

1#include <iostream>2#include <random>3#include <string>4#include <vector>5
6void run(const std::string& name, std::vector<int> nums) {7  long long shifts = 0;8  for (int i = 1; i < std::ssize(nums); i++) {9    int card = nums[i];10    int j = i - 1;11    while (j >= 0 && nums[j] > card) {12      nums[j + 1] = nums[j];13      j--;14      shifts++;15    }16    nums[j + 1] = card;17  }18  std::cout << name << ": " << shifts << " shifts\n";19}20
21int main() {22  int n = 2000;23  std::mt19937 random(42);  // makes random numbers, from seed 4224  std::vector<int> shuffled(n), nearly(n);25  for (int i = 0; i < n; i++) shuffled[i] = random() % n;26  for (int i = 0; i < n; i++) nearly[i] = i;27  nearly[5] = 900;28  run("random", shuffled);29  run("nearly sorted", nearly);30}

• Sorting makes the smallest easy to find, groups duplicates and allows binary search.
• std::ranges::sort sorts in place with <: strings compare as text, capitals first.
• A comparator returns true when a must come before b; it must be strict: <, never <=.
• Bubble sort swaps neighbours; selection sort picks the smallest; insertion sort slides each item into a sorted hand.
• All three are O(n²); insertion sort is close to O(n) on nearly sorted data.
• A stable sort keeps equal items in their original order: std::stable_sort is, std::sort is not.

You are in a long queue at a cinema and want to know your place. You cannot see the front, so you ask the person ahead: “What is your place?” They ask the person ahead of them, and so on, until the person at the front answers “1”. Each answer comes back one step: “2”, “3”… and you add one to what you hear. Nobody solved the whole problem; each person solved a smaller one by asking the next. That is recursion: a function that calls itself on a smaller input.

Recursion

Solving a problem by solving a smaller version of the same problem.

Recursive function

A function that calls itself, each time with an input closer to the simplest case.

Base case

The simplest input, answered straight away with no further call: the front of the queue.

Recursive case

Every other input: make it smaller, call yourself, and use the answer.

1void countdown(int n) {2  if (n == 0) {3    std::cout << "Lift off\n";  // base case: stop here4    return;5  }6  std::cout << n << "\n";7  countdown(n - 1);             // recursive case: a smaller n8}9
10int main() {11  countdown(3);  // 3, 2, 1, Lift off12}

The factorial of a whole number n, written n!, is 1 × 2 × … × n: the number of ways to arrange n books on a shelf. It has a recursive definition: n! = n × (n - 1)!, and 1! = 1. That definition is already the code. The base case stops the calls; the recursive case moves towards it, because n - 1 is smaller than n.

1long long factorial(int n) {2  if (n <= 1) return 1;3  return n * factorial(n - 1);4}5
6int main() {7  std::cout << factorial(4) << "\n";  // 24: 4 × 3 × 2 × 18}

1long long power(long long base, int exp) {2  if (exp == ) return ;3  return base * power(base, );4}

When a function calls another, the computer pauses the first and remembers where it was, with all its variables. That memory is a stack frame, and the frames pile up on the call stack: a stack, like a pile of plates, where the newest goes on top and comes off first (the Data structures course covers stacks). A recursive function puts one frame per call on the pile, each with its own n.

1void show(int n) {2  if (n == 0) return;3  show(n - 1);4  std::cout << n << "\n";5}6
7int main() { show(3); }

Recursion fits lists well once you see a list as “the first item, followed by a shorter list”. The sum of {3, 5, 2} is 3 plus the sum of {5, 2}. The base case is the empty list, whose sum is 0. In C++ “the rest” is cheapest as an index: sumFrom(nums, i) is the sum of the items from index i on, so sumFrom(nums, 0) = 3 + sumFrom(nums, 1) = 3 + 5 + sumFrom(nums, 2) = 3 + 5 + 2 + sumFrom(nums, 3) = 3 + 5 + 2 + 0 = 10.