/** * Quicksort — choose a pivot, put the smaller things on one side and the * larger on the other, then do the same to each side. */ function quicksort(xs: number[]): number[] { if (xs.length <= 1) { return xs; } const [pivot, ...rest] = xs; return [ ...quicksort(rest.filter((x) => x < pivot)), pivot, ...quicksort(rest.filter((x) => x >= pivot)), ]; } console.log(quicksort([5, 3, 8, 1, 9, 2, 7]).join(" "));

/** * Fisher-Yates — walk backwards, swapping each element with one drawn from * the part not yet visited. */ // Seeded, so the museum's copy shuffles the same way every time. A real // shuffle deserves a better source of randomness than this; the loop below is // what is on display. let state = 2463534242; const random = (): number => { state ^= state << 13; state ^= state >>> 17; state ^= state << 5; return (state >>> 0) / 4294967296; }; function shuffle<T>(items: readonly T[]): T[] { const xs = [...items]; for (let i = xs.length - 1; i > 0; i--) { // j is drawn from 0..i inclusive — including i, which is what makes

/** * Binary search — halve the range until the answer is cornered. */ function search(sorted: number[], target: number): number { let low = 0; let high = sorted.length - 1; while (low <= high) { // Not (low + high) / 2. That sum can overflow a fixed-width integer, // which is the bug that sat in the JDK for nine years. const mid = low + Math.floor((high - low) / 2); if (sorted[mid] === target) { return mid; } if (sorted[mid] < target) { low = mid + 1; } else { high = mid - 1; }

/** * Floyd's cycle detection — two walkers at different speeds. If the path * loops, the fast one comes round and meets the slow one. */ type Node = { value: string; next?: Node }; function hasCycle(start: Node): boolean { let slow: Node | undefined = start; let fast: Node | undefined = start; while (fast?.next) { slow = slow?.next; fast = fast.next.next; if (slow === fast) { return true; } } return false; }

/** * Boyer-Moore majority vote — find the value appearing more than half the * time, in one pass, remembering one candidate and one number. */ function majority<T>(items: readonly T[]): T | undefined { let candidate: T | undefined; let count = 0; for (const item of items) { if (count === 0) { candidate = item; } count += item === candidate ? 1 : -1; } // The pass only promises an answer when a majority exists, so the claim // has to be checked before it is believed. const seen = items.filter((x) => x === candidate).length; return seen * 2 > items.length ? candidate : undefined; }

Gallery of Methods

Shown as a list, because your system asks for reduced motion.

Continue to Hall of the Commons →

Commissioned for this museum · after Robert W. Floyd, 1967

The Tortoise and the Hare

TypeScript·1967·30 lines·622 bytes

/**
 * Floyd's cycle detection — two walkers at different speeds. If the path
 * loops, the fast one comes round and meets the slow one.
 */
type Node = { value: string; next?: Node };

function hasCycle(start: Node): boolean {
	let slow: Node | undefined = start;
	let fast: Node | undefined = start;

	while (fast?.next) {
		slow = slow?.next;
		fast = fast.next.next;
		if (slow === fast) {
			return true;
		}
	}

	return false;
}

const a: Node = { value: "a" };
const b: Node = { value: "b" };
const c: Node = { value: "c" };
a.next = b;
b.next = c;

console.log(hasCycle(a));
c.next = a;
console.log(hasCycle(a));

Curator’s note

The obvious way to find a loop is to remember where you have been: keep a set of visited nodes, and stop when you see one twice. It works, it is easy to argue for, and it costs memory proportional to the length of the path. This uses two variables. That is the whole exhibit — the same answer, in constant space, and the trick is that you do not have to remember anything if you have someone slower to compare against.

Why it works is easier to feel than to prove. Once both walkers are inside the loop, the fast one gains exactly one step on the slow one per iteration, so the gap between them closes by one each time and cannot skip past zero. If there is a cycle they must meet; if there is not, the fast one runs off the end. The argument is four sentences long and still surprises people who have known the algorithm for years.

It is a small thing to notice that fast?.next guards two dereferences. Advancing the hare by two means checking that both steps exist, and the version of this bug people actually write is checking one and crashing on the other — usually on a list of length two, which is exactly the case nobody tests.

Floyd published it in 1967 in the context of detecting cycles in sequences rather than lists, which is where it still earns its keep: Pollard's rho algorithm uses it to factor integers, and random number generators are tested for their period the same way. Its most common use today is a job interview, which is a slightly undignified retirement for a genuinely clever idea.