The classic algorithms

The idea takes one sentence. Getting it exactly right is famously fiddly — most programmers write it wrong on their first attempt, usually by mishandling the boundaries or looping forever when two items remain.

Be deliberate about three things: whether your high boundary is included or one past the end, whether the loop condition uses less-than or less-than-or-equal, and how the boundaries move after each comparison. Pick one convention and use it every time.

The genuinely powerful version is binary searching on the answer. If a question is “what is the smallest capacity that gets this job done in time”, and you can cheaply test whether any given capacity works, you can binary search over the possible capacities without any sorted list existing at all. This turns up constantly and is worth practising specifically.

You already met it: the number-guessing game in week 2 was binary search with a human doing the halving.

The slow ones first, because they teach the vocabulary. Bubble sort repeatedly swaps neighbours that are out of order. Selection sort repeatedly finds the smallest remaining item. Insertion sort takes each item and slides it back into place among those already sorted. All three are O(n²) and none is used for large data.

Insertion sort is the exception worth knowing: it is genuinely fast on small or nearly-sorted input, and real sorting libraries switch to it for small chunks. Do not dismiss it.

The fast ones are O(n log n). Merge sort splits the list in half, sorts each half, and merges the two sorted halves — it is stable and it can sort files larger than memory, because merging only ever looks at the front of each piece. Quicksort picks a pivot, moves smaller things left and larger things right, and recurses — it is in-place and usually fastest in practice, but a bad pivot choice degrades it to O(n²). Heapsort uses the heap from week 20 and guarantees O(n log n), at the cost of being slower in practice than quicksort.

Stability matters more than beginners expect. A stable sort leaves equal items in their existing order, which lets you sort by one field and then another and keep both — sort by name, then by department, and within each department the names are still in order. An unstable sort silently loses that.

There are also sorts that do not compare at all. Counting sort and radix sort exploit the values being bounded integers and can beat O(n log n), but only under those conditions.

What you actually use: Python's sorted() is Timsort, a hybrid of merge sort and insertion sort that detects runs already in order and exploits them. It is stable and very good. Write your own sorts to learn; use sorted() thereafter.

Breadth-first uses a queue and visits everything one step away, then everything two steps away. That ordering is exactly why it finds the shortest route when every step costs the same — the first time it reaches somewhere is by the fewest steps.

Depth-first uses a stack, or recursion, which is the same thing. It goes as deep as it can and then backtracks. It is the natural fit for detecting cycles, finding connected components, and topological ordering.

The pair differ by one line: whether you take the next item from the front of a queue or the top of a stack. Noticing that is a genuinely useful moment — the exploration strategy is entirely determined by the structure holding the frontier.

Both must keep a visited set. Without it, a cycle makes them loop forever. This is the single most common bug in graph code.

Breadth-first search finds the shortest path only when every step costs the same. Once roads have different lengths, you need something cleverer.

Dijkstra's algorithm is the one to know properly. It keeps a priority queue of places to visit next, always expanding whichever is cheapest to reach so far. It is what powers turn-by-turn navigation. Its one condition is that no connection may have a negative cost — with negative costs its central assumption breaks.

Bellman-Ford is slower but handles negative costs, and can detect a negative cycle — a loop you could go round forever getting cheaper. That sounds artificial until you realise a negative cycle in a currency-exchange graph is an arbitrage opportunity, which is a real thing people build systems to find.

Floyd-Warshall computes the shortest path between every pair at once. It is three nested loops and about five lines, which makes it disarmingly simple, but the cost is the cube of the vertex count — fine for a few hundred places, hopeless for a million.

A-star is Dijkstra plus a hint. If you are routing on a map and know roughly which direction the destination lies, you can prefer paths heading that way and skip exploring in the wrong direction. It is the standard choice in games.

Kruskal's algorithm sorts every connection by cost and adds them cheapest-first, skipping any that would form a loop. Checking for that loop is exactly what union-find from week 24 does, which is why the two are always taught together.

Prim's algorithm instead grows outwards from one starting point, repeatedly adding the cheapest connection that reaches somewhere new. It uses a heap, in the same way Dijkstra does.

Both give a correct answer, and the choice between them depends on whether your graph has many connections or few. They are a clean illustration of greedy algorithms being provably right for certain problems — which sets up week 31.

It only works on a directed graph with no cycles. If your dependencies contain a cycle — A needs B, B needs A — there is no valid order at all, and detecting that is half the value of running it.

Two ways to do it. Kahn's algorithm repeatedly takes anything with no remaining dependencies, outputs it, and removes it. Or run depth-first search and output nodes in reverse finishing order.

You have already benefited from this many times. Every time npm or pip works out install order, every time a build system decides what to compile first, every time a spreadsheet recalculates cells in the right order, that is a topological sort. The error message about a circular dependency is this algorithm detecting a cycle.