Track 3
Algorithms
Step-by-step methods for searching, sorting and finding paths, and how to compare them with Big O.
9 pages, each with a live figure. Read them in order: later pages build on earlier ones.
- 3.1Big OSlidersA way to describe how an algorithm's work grows as its input grows, ignoring constant factors.
- 3.2Binary searchStep throughFind a value in a sorted list by checking the middle and throwing away the half it can't be in.
- 3.3Bubble sortPlaygroundWalk the list swapping neighbours that are out of order; each pass carries the largest remaining value to the end.
- 3.4Insertion sortPlaygroundGrow a sorted section at the front, sliding each new value left until it fits.
- 3.5Merge sortPlaygroundSplit the list in half, sort each half, then merge the two sorted halves into one.
- 3.6QuicksortPlaygroundPick a pivot, move every smaller value to its left, then sort each side the same way.
- 3.7Comparing sorting algorithmsRaceNo sort is fastest everywhere. The best choice depends on the input's size and order, and on whether you need stability or little memory.
- 3.8Graph traversalExplorerVisit every node you can reach from a start node, using a queue to go wide first or a stack to go deep first.
- 3.9Dijkstra's algorithmExplorerFind the shortest distance from one node to every other by always settling the closest node not yet settled.