TDD on the CPC: selection sort, and what it costs

24/10/2026Z80CPCTDDsorting

How long does a CPC take to sort 255 bytes? On a PC, we answer “O(n²)” and move on, but on the CPC we want NOPs. So we are going to write a selection sort in Z80, one test at a time, all the way to an exact formula for its duration, itself checked by a test.

Along the way, we run into two surprises: tests that failed only by luck, and a worst case that is not the reversed array.

The starting point is the find_min routine and its tests, written in the previous post, which also presents the method.

What the routine does

HL points at the array, B holds its length (1 to 255), and the routine sorts the array in place, smallest first. As for find_min, the array stays within one 256-byte page.

Selection sort finds the smallest byte of the array and swaps it with the first one, which is then in its place. Then it starts again on the rest, up to the last byte. You can play the animation or go step by step: the arrow shows the byte being read, the filled box the current minimum, and the boxes with a coloured outline the bytes already in their place.

Complexity, in NOPs

The complexity of an algorithm describes how its duration grows with the size of the data. Let’s take find_min as the previous post left it (intro/11-green), and run it on longer and longer arrays. In the worst case, each byte is a new minimum (falling bytes). In the best case, the first byte is already the smallest (rising bytes). Here are the measured durations, in NOPs:

The count can be done by hand, as for the budget of the previous post, starting from the 5 NOPs of the entry. A turn where the minimum changes costs 11: inc l 1, cp (hl) 2, jr c 2 when it does not jump, ld a,(hl) 2, djnz 4. A turn where it does not change costs 10, because jr c jumps (3 NOPs) over ld a,(hl). With n − 1 turns, a last djnz that is 1 NOP cheaper and the final ret, we get 11n − 4 NOPs in the worst case, and 10n − 3 in the best case.

If n doubles, the duration doubles: find_min is linear, which computer scientists write O(n), “proportional to n, up to a constant”. The O() throws the constant away, whereas on the CPC it is often what matters (here, 11 NOPs per byte).

Selection sort calls find_min on n bytes, then on n − 1, and so on down to 2. The sum of these lengths is about n²/2: when n doubles, the duration is multiplied by four. That is O(n²). What is left is to write the sort, then to find the exact formula.

The first test

The code starts from the end of the previous post: find_min and its six tests. Once selection-sort.asm exists (selection/02-green), the main source includes both routines:

 org #4000
 include "find-min.asm"
 include "selection-sort.asm"

As a reminder, a test puts values in the registers and in memory, calls the routine, then compares the result with what we expect. In every test of the post, HL is #8000 and B the length of the array, so the test tables only show the bytes and the expected result. The tests call selection_sort, except two that call find_min, and their table says so.

A one-byte array is already sorted. The first test only checks that the routine leaves the memory alone:

// Runs selection_sort on `bytes`, written at ARRAY.
function selectionSort(bytes: number[]) {
  return program.run("selection_sort", {
    registers: { hl: ARRAY, b: bytes.length },
    memory: [{ at: ARRAY, bytes }],
  });
}

it("leaves a one-byte array as it is", () => {
  expect(selectionSort([0x42])).toLeaveMemoryUnchanged();
});

One byte, then two

The first test fails for the right reason: the routine does not exist yet (selection/01-red):

Error: The Program has no label "selection_sort"

Here is the least code possible to go green (selection/02-green):

selection_sort:
 ret

It is the same cheat as in the previous post: the routine sorts nothing. Two bytes in the wrong order expose it (selection/03-red):

it("swaps two bytes in the wrong order", () => {
  expect(selectionSort([0x42, 0x17]).memory(ARRAY, 2)).toEqual([0x17, 0x42]);
});

The routine leaves the two bytes in the wrong order:

AssertionError: expected [ 66, 23 ] to deeply equal [ 23, 66 ]

This message comes from Vitest, the tool that runs the tests, not from z80-tdd, hence the bytes in decimal: 66 is #42, and 23 is #17. z80-tdd cannot yet compare an area of memory with expected bytes, and we have to read the decimal. For two bytes, one comparison and one swap are enough, still without a loop (selection/04-green):

selection_sort:
 dec b
 ret z
 ld a,(hl)
 inc l
 cp (hl)
 ret c          ; the two bytes are already in order
 ld b,(hl)
 ld (hl),a
 dec l
 ld (hl),b
 ret

find_min must say where

From three bytes on, the minimum must be swapped with the first byte, which means knowing where it is. But find_min only returns its value. Before we write the loop, we therefore add a test to find_min (selection/05-red):

it("returns in DE the address of the smallest byte", () => {
  expect(findMin([0x42, 0x30, 0x05, 0x17, 0x99])).toHaveRegisters({ de: ARRAY + 2 });
});

The routine does not touch DE yet:

Error: Registers differ:
  DE  expected #8002, received #0000

As the array stays within one page, D never changes and takes the page of H at entry. Only E follows the minimum (selection/06-green):

find_min:
 ld d,h
 ld e,l
 ld a,(hl)
 dec b
 ret z
.loop:
 inc l
 cp (hl)
 jr c,.next     ; A is below this byte
 ld a,(hl)
 ld e,l
.next:
 djnz .loop
 ret

The new test passes, but an old one falls, the budget of 172 NOPs on 16 falling bytes:

AssertionError: expected 189 to be less than or equal to 172

The budget of the previous post does its job. The count is quick: ld d,h and ld e,l add 2 NOPs at entry, and ld e,l adds 1 NOP to each of the 15 turns where the minimum changes, which gives 172 + 2 + 15 = 189. We see no cheaper version, since A and the address must both change at each new minimum. So we raise the budget to 189 NOPs, knowingly, and the test says why in a comment:

it("finds the smallest of 16 bytes in 189 NOPs at most", () => {
  // Falling bytes make every turn of the loop take its slower path.
  const falling = Array.from({ length: 16 }, (_, i) => 0xff - i);

  // The address in DE costs 2 NOPs at entry and 1 NOP for each new minimum.
  expect(findMin(falling).nops).toBeLessThanOrEqual(189);
});

The loop

The next test sorts five shuffled bytes (selection/07-red):

it("sorts five bytes in any order", () => {
  expect(selectionSort([0x42, 0x30, 0x05, 0x17, 0x99]).memory(ARRAY, 5)).toEqual([
    0x05, 0x17, 0x30, 0x42, 0x99,
  ]);
});

The two-byte version fails:

AssertionError: expected [ 48, 66, 5, 23, 153 ] to deeply equal [ 5, 23, 48, 66, 153 ]

In hexadecimal, the routine left #30, #42, #05, #17, #99: it swapped the first two bytes, then stopped. Now it is time to write the real loop (selection/08-green):

; Sorts in place, smallest first, the array at HL, B bytes long (1 to 255).
; The array stays within one 256-byte page, as find_min requires.
selection_sort:
 dec b          ; one pass for each byte but the last
 ret z
.loop:
 push bc
 push hl
 inc b          ; find_min scans the bytes not yet sorted: B + 1
 call find_min
 pop hl
 pop bc
 ld c,(hl)      ; swap the smallest byte with the first unsorted one
 ld (hl),a
 ld a,c
 ld (de),a
 inc l
 djnz .loop
 ret

All the tests are now green. There are n − 1 passes, because the last byte is sorted once all the others are. find_min moves L and empties B, hence the push and pop around the call. When the minimum is already in place, DE equals HL and the byte swaps with itself: that changes nothing, and a test to avoid it would cost NOPs on every pass.

Tests that failed by luck

A test that passes as soon as it is written must prove that it can fail: we break the routine on purpose, and check that it turns red. The previous post calls these tests guards. Here, breaking the routine reveals a hole in the tests already written.

Let’s drop the dec b at entry. Each pass then asks find_min for one byte too many, the one that follows the array, and the sort makes one more pass. The sort tests fail at once, and the one-byte test shows the extra swap:

Error: Memory changed:
  #8000  #42 -> #00
  #8001  #00 -> #42

But they fail only because each test starts from fresh memory, filled with #00. This zero, smaller than any byte, gets into the array. With #FF after the array, find_min would never pick it, and the broken version would pass every test.

The tests depended on a condition they did not state, and the next guard states it out loud, by writing #00 right after the array itself (selection/09-guard):

it("ignores a smaller byte right after the array", () => {
  // Fresh memory already holds #00 there: this test says so out loud.
  const run = program.run("selection_sort", {
    registers: { hl: ARRAY, b: 5 },
    memory: [{ at: ARRAY, bytes: [0x42, 0x30, 0x05, 0x17, 0x99, 0x00] }],
  });

  expect(run).toChangeOnly({ address: ARRAY, length: 5 });
  expect(run.memory(ARRAY, 5)).toEqual([0x05, 0x17, 0x30, 0x42, 0x99]);
});

It passes as soon as it is written, and with the version without dec b, it gives the faulty address, in hexadecimal this time:

Error: Memory changed outside #8000-#8004:
  #8005  #00 -> #99

The real worst case

The formula promised at the start is still to come, and to write it, we need the array that makes the sort suffer most. We would think of the reversed array, but the measurement says otherwise (durations in NOPs):

Equal bytes are the worst case. With two equal bytes, cp (hl) does not set the carry, so find_min takes a new minimum at each byte. In a reversed array, on the other hand, the swaps put some order back pass after pass, and some turns take the short path: 56 turns out of 120 for 16 bytes.

Here is the count for n equal bytes. On m bytes, find_min costs 12m − 3 NOPs: 7 at entry, 12 per turn, 1 less for the last djnz, 3 for the ret. The sort adds 32 NOPs around each call: push bc 4, push hl 4, inc b 1, call 5, pop hl 3, pop bc 3, ld c,(hl) 2, ld (hl),a 2, ld a,c 1, ld (de),a 2, inc l 1, djnz 4.

The passes cover m = n, n − 1, … down to 2 bytes, and the sum gives 6n² + 35n − 36 NOPs: O(n²), with its constants.

The last guard sets this ceiling for three lengths (selection/10-guard):

// Equal bytes are the slowest input: find_min takes a new minimum at each byte.
it.each([2, 16, 255])("sorts %i equal bytes in 6n² + 35n − 36 NOPs at most", (n) => {
  const equal = Array.from({ length: n }, () => 0x42);

  expect(selectionSort(equal).nops).toBeLessThanOrEqual(6 * n * n + 35 * n - 36);
});

This guard catches a classic temptation: put inc hl back into find_min to lift the page constraint. That is 1 NOP more per turn of find_min, and the sort makes n(n − 1)/2 turns in its calls. All three cases fall:

AssertionError: expected 59 to be less than or equal to 58
AssertionError: expected 2180 to be less than or equal to 2060
AssertionError: expected 431424 to be less than or equal to 399039

The budget of find_min falls too (expected 204 to be less than or equal to 189): it sees the extra cost on 16 bytes. The guard, for its part, says what this extra cost means for the sort: 32 385 more NOPs on 255 bytes.

For 255 bytes, the sort takes at most 399 039 NOPs, that is about 20 frames of 19 968 NOPs. Here is the answer to the question at the start: 0.4 seconds.

Conclusion

With z80-tdd, complexity is measured to the NOP, and a test sets it. Selection sort keeps its O(n²), but its constants are now written down, and a future optimisation can no longer make them worse without making a guard fall.

The sort keeps the restrictions of find_min: 1 to 255 bytes, within one 256-byte page. It also makes a useless swap when the minimum is already in place.

The next post moves on to insertion sort, with the same hunt for its worst case.

Trying it yourself

You need Node.js 24 or later, pnpm, and RASM v3.3.1 on the PATH. The steps of this post are on the selection branch of the z80-tdd-sorts repository, which starts from the last tag of the previous post. To replay a step:

git checkout selection/01-red
pnpm install
pnpm test

On the selection/* tags, the --no-lockfile option is no longer needed: the first commit of the branch fixes the lockfile that pnpm 10.34.1 or later refused.

The tests of the sort are in src/selection-sort.test.ts, next to those of find_min. To install z80-tdd in a project of your own, see the Trying it yourself section of the previous post.

Links

• The previous post: find_min and the introduction to TDD on the CPC
• z80-tdd, the test tool
• z80-tdd-sorts, the repository of this post (branch selection)
• RASM, the assembler by Édouard Bergé (Roudoudou)
• Perfectly accurate Z80 flags and CPC timing, Madram / Overlanders (64NOPS), the table of durations in NOPs