Gallery of Methods

Continue toHall of the Commons

/**
 * 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(" "));

Quicksort

TypeScript · 1961

/**
 * 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

An Honest Shuffle

TypeScript · 1964

/**
 * Euclid's algorithm — the greatest common divisor, by taking remainders
 * until nothing is left over.
 */
function gcd(a: number, b: number): number {
	while (b !== 0) {
		[a, b] = [b, a % b];
	}
	return a;
}

console.log(gcd(1071, 462));
console.log(gcd(270, 192));

The Oldest One Here

TypeScript · 1956

/**
 * 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;
		}

Binary Search

TypeScript · 1946

/**
 * 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;
}

The Tortoise and the Hare

TypeScript · 1967

/**
 * 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;
}

The Majority

TypeScript · 1981