STRATEGY / THE WALKTHROUGH

One job.
More than one way to do it.

Learn why interchangeable algorithms can make a system easier to change.

THE STARTING POINT

Put a list of numbers in order.

You’re building a sorting tool. Someone gives it numbers; it returns the same numbers from smallest to largest. Bubble Sort already does the job.

Try it: sort the list in the tool.

Chapter 1 of 3 · Continue whenever you’re ready.

Your sorting tool

LIVE EXAMPLE

ORIGINAL INPUT

Try your own numbers

SORTING ALGORITHM

Bubble Sort Our starting choice

One function does the work.

RESULT

Your sorted result will appear here.

Curious how the algorithm works?

Optional deep dive. These are real algorithm events, not a speed benchmark.

Current list: [5, 1, 4, 2, 3]

Outlined = active positions · ✓ = settled position

Reduced motion: step through instant snapshots, or show the result immediately.

Ready

Choose Next event to inspect the first operation.

0 comparisons · 0 swaps

Watch the code do the work

Compare neighbors, exchange only when left is larger, and finish each pass with one more settled position. A pass without swaps stops the loop early.

export function bubbleSort(input: readonly number[]): SortRun {
  const items = input.map((value, id) => ({ value, id }));
  const events: SortEvent[] = [];
  for (let end = items.length - 1; end > 0; end--) {
    let swapped = false;
    for (let i = 0; i < end; i++) {
      const left = items[i].value,
        right = items[i + 1].value;
      record(
        events,
        items,
        "compare",
        "bubble-compare",
        [i, i + 1],
        end + 1,
        `${left} ${left > right ? ">" : "≤"} ${right}: ${left > right ? "exchange these neighbors next." : "keep their order."}`,
      );
      if (left > right) {
        [items[i], items[i + 1]] = [items[i + 1], items[i]];
        swapped = true;
        record(
          events,
          items,
          "swap",
          "bubble-swap",
          [i, i + 1],
          end + 1,
          `Exchanged ${left} and ${right}. The larger value moved one place right.`,
        );
      }
    }
    record(
      events,
      items,
      "pass-complete",
      "bubble-pass",
      [],
      swapped ? end : 0,
      swapped
        ? `Pass finished. Positions ${end + 1}–${items.length} are settled.`
        : "No swaps this pass: the entire list is already sorted. Stop early.",
    );
    if (!swapped) break;
  }
  record(
    events,
    items,
    "done",
    "bubble-done",
    [],
    0,
    "Ascending order reached. The original input is unchanged.",
  );
  return { input: [...input], output: items.map((item) => item.value), events };
}

Highlighted concept: copy-input. The record calls save snapshots of actual operations for the animation.

Data types and trace recorder

export type Item = Readonly<{ id: number; value: number }>;
export type Anchor =
  | "copy-input"
  | "bubble-compare"
  | "bubble-swap"
  | "bubble-pass"
  | "bubble-done"
  | "quick-pivot"
  | "quick-compare"
  | "quick-swap"
  | "quick-partition"
  | "quick-done"
  | "insertion-compare"
  | "insertion-swap"
  | "insertion-done";
export type SortEvent = Readonly<{
  kind:
    | "compare"
    | "swap"
    | "pass-complete"
    | "pivot"
    | "partition-complete"
    | "done";
  anchor: Anchor;
  items: readonly Item[];
  indices: readonly number[];
  settledFrom: number;
  caption: string;
  range?: readonly [number, number];
  pivot?: number;
  boundary?: number;
  settled?: readonly number[];
}>;
export type SortRun = Readonly<{
  input: readonly number[];
  output: readonly number[];
  events: readonly SortEvent[];
}>;

// Instrumentation records immutable snapshots of the real working list.
function record(
  events: SortEvent[],
  items: Item[],
  kind: SortEvent["kind"],
  anchor: Anchor,
  indices: number[],
  settledFrom: number,
  caption: string,
) {
  events.push({
    kind,
    anchor,
    items: items.map((item) => ({ ...item })),
    indices: [...indices],
    settledFrom,
    caption,
  });
}

This is the same TypeScript function that computes the visualization.

Bubble Sort has O(n) best-case and O(n²) average/worst-case work. This last-pivot Quick Sort averages O(n log n), but can take O(n²), including sorted or equal-valued input. Neither is always faster. Bubble Sort preserves equal-value order; this Quick Sort does not promise stability.

THE SIMPLE IDEA

Input → algorithm → result

INPUTUnsorted numbers

ONE FUNCTIONBubble Sort

OUTPUTAscending numbers

Keep the original list intact. Return ascending values, including duplicates. This promise stays the same for the entire lesson.

OPTIONAL · PUT IT INTO PRACTICETry the next requirement

Add Insertion Sort. Keep the promise.

A third algorithm is ready. Your task is to make it available without reopening Sorter. Choose the changes, then check that the replacement behaves as callers expect.

Inspect the supplied TypeScript implementation

It sorts a copy, preserves duplicates, and records its real operations. You do not need to learn the sorting loop to answer the questions.

import type { Item, SortEvent, SortRun } from "./sorting.ts";
import type { SortStrategy } from "./strategies.ts";

// Supplied for the transfer check; no changes to Sorter or SortStrategy.
export class InsertionSort implements SortStrategy {
  sort(input: readonly number[]): SortRun {
    const items: Item[] = input.map((value, id) => ({ value, id }));
    const events: SortEvent[] = [];
    const record = (
      kind: "compare" | "swap" | "done",
      indices: number[],
      caption: string,
    ) => {
      events.push({
        kind,
        anchor:
          kind === "compare"
            ? "insertion-compare"
            : kind === "swap"
              ? "insertion-swap"
              : "insertion-done",
        items: items.map((item) => ({ ...item })),
        indices: [...indices],
        settledFrom: kind === "done" ? 0 : items.length,
        caption,
      });
    };
    for (let i = 1; i < items.length; i++) {
      for (let j = i; j > 0; j--) {
        record(
          "compare",
          [j - 1, j],
          "Compare neighbors in the growing sorted prefix.",
        );
        if (items[j - 1].value <= items[j].value) break;
        [items[j - 1], items[j]] = [items[j], items[j - 1]];
        record("swap", [j - 1, j], "Move the smaller value one place left.");
      }
    }
    record(
      "done",
      [],
      "Ascending order reached. The original input is unchanged.",
    );
    return {
      input: [...input],
      output: items.map((item) => item.value),
      events,
    };
  }
}

1. Where should the change happen?

Select every required change.

Add the supplied InsertionSort implementation.Add an Insertion Sort branch inside Sorter.Register the new option where the caller chooses a strategy.Change SortStrategy to accept an algorithm name.Duplicate the sorting screen for the new algorithm.

2. Another version sorts the caller’s list in place. Is it a safe replacement?Yes. Returning sorted values is the whole contract.No. It must sort a copy so the caller keeps the original input.Yes. A readonly or List type guarantees nothing can mutate the input.

3. With input [3, 1, 3, 2], what should the caller see?Result [1, 2, 3]; original [3, 1, 3, 2].Result [1, 2, 3, 3]; original [1, 2, 3, 3].Result [1, 2, 3, 3]; original [3, 1, 3, 2].

No timer or attempt limit. Change an answer and check again whenever you’re ready.

Can you use Strategy in another setting?

Keep the idea, change the problem. Build a checkout with interchangeable shipping rules.

Try a new challenge →