TDD on the CPC: bubble sort, the flag or Knuth's bound

24/10/2026Z80CPCTDDsorting

The insertion sort of the previous post makes use of the order it finds in the array. Bubble sort is the most famous of the simple sorts, and also the most mocked. On a Z80, does it deserve its reputation?

We are going to check by writing it in Z80, one test at a time. A budget test decides between several versions, the textbook one among them, and then the three sorts face each other.

The method is that of the post on find_min, to read first if TDD is new to you.

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. It is the contract of the two previous sorts, and the array still stays within one 256-byte page.

We walk through the array, and compare each byte with its right neighbour. If the neighbour is smaller, the two swap places. The largest byte seen so far thus moves up to the end of the array, like a bubble that rises: it is the bubble. So one pass puts at least one byte in its place, the last one. We start again until the array is sorted.

Play the animation, or go step by step: the filled box shows the bubble, the arrow the byte compared with the bubble, and the boxes with a coloured outline the bytes already in place, at the end of the array. The animation shows the final version of the post: a pass stops where the one before made its last swap. The section on the budget explains why.

On an array already sorted, the first pass swaps nothing. On a reversed array, every comparison swaps. The tests will measure both cases later on.

The first test

Like insertion sort, bubble sort does not need find_min. The code starts from scratch, and the main source includes only the new routine:

 org #4000
 include "bubble-sort.asm"

In the tests of this post, HL is #8000 and B the length of the array. So the test tables only show the bytes and the expected result. The arrays of 1, 2 and 5 bytes are the same as for the two previous sorts, to compare the three sorts at the end.

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

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

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

One byte, then two

The first steps follow those of the two previous sorts. The one-byte test fails for lack of a label (bubble/01-red), and a plain ret makes it pass (bubble/02-green). Two bytes in the wrong order expose that cheat (bubble/03-red):

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

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

Vitest shows the bytes in decimal: 66 is #42, and 23 is #17. The green code compares the two bytes, and swaps them if they are in the wrong order. One detail matters already: the left byte, the bubble, stays in E (bubble/04-green):

bubble_sort:
 dec b
 ret z
 ld e,(hl)      ; E: the bubble, the left byte of the pair
 inc l
 ld a,(hl)
 cp e
 ret nc         ; the two bytes are already in order
 ld (hl),e      ; swap them
 dec l
 ld (hl),a
 ret

One pass

The next test puts the largest byte at the head of a sorted run. A single pass must take it to the end (bubble/05-red):

it("moves the first byte to the end of a sorted run", () => {
  expect(bubbleSort([0x42, 0x05, 0x17, 0x30]).memory(ARRAY, 4)).toEqual([
    0x05, 0x17, 0x30, 0x42,
  ]);
});

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

In hexadecimal, the routine left #05, #42, #17, #30: only the first pair moved. The pass becomes a loop over the pairs, and B counts them. If the next byte is smaller than the bubble, we write the bubble on its right and the byte on its left: the bubble moves one place on. Otherwise, the bubble stops, and the next byte becomes the bubble (bubble/06-green):

bubble_sort:
 dec b          ; B: the pairs to compare
 ret z
 ld e,(hl)      ; E: the bubble, the largest byte so far
.pair:
 inc l
 ld a,(hl)
 cp e
 jr nc,.drop    ; the next byte is not below the bubble
 ld (hl),e      ; swap them: the bubble moves one place right
 dec l
 ld (hl),a
 inc l
 djnz .pair
 ret
.drop:
 ld e,a         ; the bubble stops, and the next byte becomes the bubble
 djnz .pair
 ret

The bubble stays in E because it has already been read: without E, each pair would read both its bytes from memory again.

All the passes

The next test sorts five mixed bytes (bubble/07-red):

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

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

In hexadecimal, the routine left #30, #05, #17, #42, #99. The pass did push #42 up against #99, but the start is still out of order. The pass must be repeated, once per pair. C counts the passes, and the stack keeps B and HL so that each pass starts again from the first byte (bubble/08-green):

bubble_sort:
 dec b          ; B: the pairs to compare in each pass
 ret z
 ld c,b         ; C: the passes left, one for each pair
.pass:
 push bc
 push hl
 ld e,(hl)      ; E: the bubble, the largest byte so far
.pair:
 inc l
 ld a,(hl)
 cp e
 jr nc,.drop    ; the next byte is not below the bubble
 ld (hl),e      ; swap them: the bubble moves one place right
 dec l
 ld (hl),a
 inc l
 djnz .pair
 jr .end
.drop:
 ld e,a         ; the bubble stops, and the next byte becomes the bubble
 djnz .pair
.end:
 pop hl
 pop bc
 dec c
 jr nz,.pass
 ret

All the tests are green, with the textbook bubble sort: n − 1 full passes, whatever happens.

One pair too many

Insertion sort moved back through the array, and it needed a wall before the first byte. Bubble sort moves forward by inc l, and its dec l only goes back to the left byte of the pair: nothing reads before the array. The danger is on the other side: with one pair too many, the pass pulls into the array the byte that follows it.

The next test passes as soon as it is written: it is a guard. A guard must prove that it can fail. So we break the routine on purpose, and check that it turns red. This guard puts a smaller byte right after the array (bubble/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("bubble_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]);
});

The broken version it aims at adds an inc b after the ld c,b: each pass compares one pair too many. The guard sees it:

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

But the three sort tests fail too:

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

Vitest writes zero as +0. In hexadecimal, the first test expected #17, #42 and finds #17, #00. In all three arrays, the #00 that follows the array has taken the place of the largest byte, pushed out.

In the previous post, the #00 of fresh memory hid a bug. Here, it gives one away: it is the smallest possible byte, and the extra pair brings it into the array. So the older tests catch the broken version, but by luck, whereas the guard writes that #00 down in black and white.

The budget turns down the flag

Everything is green, but the routine makes all its passes, even on an array already sorted. The next test sets a budget, a number of NOPs not to go over, for 2, 16 and 255 sorted bytes (bubble/10-red):

// Sorted bytes are the fastest input: one pass finds no swap, and the sort stops.
it.each([2, 16, 255])("sorts %i sorted bytes in 12n + 6 NOPs at most", (n) => {
  const sorted = Array.from({ length: n }, (_, i) => i);

  expect(bubbleSort(sorted).nops).toBeLessThanOrEqual(12 * n + 6);
});

Unlike those of insertion sort, this budget is not a guard: it fails, and it drives the code forward. It aims at a single pass with no swap, then the exit. The code of 08-green is far from it:

AssertionError: expected 37 to be less than or equal to 30
AssertionError: expected 2991 to be less than or equal to 198
AssertionError: expected 779024 to be less than or equal to 3066

For 255 bytes already sorted, the routine makes 254 passes without a single swap, and takes 779 024 NOPs, that is 39 frames of 19 968 NOPs.

The classic answer is a flag: if a pass swaps nothing, the array is sorted, and we stop. Three touches do it:

• an ld d,0 at the start of the pass;
• an ld d,1 at each swap;
• after the pop bc, a dec d followed by a ret nz.

All the sort tests stay green, but the budget still fails:

AssertionError: expected 38 to be less than or equal to 30
AssertionError: expected 206 to be less than or equal to 198
AssertionError: expected 3074 to be less than or equal to 3066

The budget is missed by 8 NOPs, whatever the size. The flag does stop the sort after one pass, but it adds to the pass counter instead of replacing it. The ld c,b, the push bc and the pop bc stay, and the ld d,0 and the dec d come on top.

Donald Knuth has a better idea, Algorithm B of The Art of Computer Programming (volume 3, §5.2.2). We remember the position of the last swap. All the bytes after it are in their place, so the next pass stops there. If a pass swaps nothing, the bound stays at the first byte, and the sort stops. A single register replaces both the pass counter and the flag (bubble/11-green):

; Sorts in place, smallest first, the array at HL, B bytes long (1 to 255).
; The array stays within one 256-byte page: INC L never carries into H.
; Knuth's Algorithm B (TAOCP 5.2.2): a pass stops at the last swap of the pass before.
bubble_sort:
 dec b          ; B: the pairs to compare in this pass
 ret z
.pass:
 push hl
 ld d,l         ; D: L at the left byte of the last swap; with no swap, L at the first byte
 ld e,(hl)      ; E: the bubble, the largest byte so far
.pair:
 inc l
 ld a,(hl)
 cp e
 jr nc,.drop    ; the next byte is not below the bubble
 ld (hl),e      ; swap them: the bubble moves one place right
 dec l
 ld (hl),a
 ld d,l
 inc l
 djnz .pair
 jr .end
.drop:
 ld e,a         ; the bubble stops, and the next byte becomes the bubble
 djnz .pair
.end:
 pop hl
 ld a,d
 sub l          ; the pairs before the last swap: the bytes after its left byte are in place
 ret z
 ld b,a
 jr .pass

D keeps L on the left byte of the last swap. After the pass, sub l gives the number of pairs before it: that is the length of the next pass. If it is zero, ret z ends the sort. C is gone, and the stack only keeps HL.

As for insertion sort, the count can be done by hand. A pair with no swap costs 12 NOPs: inc l 1, ld a,(hl) 2, cp e 1, jr nc 3, ld e,a 1, djnz 4.

The sum gives 12n + 6 NOPs. The budget is met exactly, without a single NOP to spare.

The guards

The last two tests pass as soon as they are written. First, equal bytes, the worst case of selection sort (bubble/12-guard). Here, as with insertion sort, they are also the best case: jr nc stops the bubble as soon as the next byte is not smaller, so the bubble never moves past an equal byte. The guard reuses the budget of sorted bytes:

// A bubble never moves past a byte equal to it.
it.each([2, 16, 255])("sorts %i equal bytes in 12n + 6 NOPs at most", (n) => {
  const equal = Array.from({ length: n }, () => 0x42);

  expect(bubbleSort(equal).nops).toBeLessThanOrEqual(12 * n + 6);
});

The broken version it aims at also swaps equal bytes: a jr z,$+4 before the jr nc jumps to the swap. The sort stays correct, but 255 equal bytes then cost 588 011 NOPs, more than 255 reversed bytes with the right version:

AssertionError: expected 39 to be less than or equal to 30
AssertionError: expected 2461 to be less than or equal to 198
AssertionError: expected 588011 to be less than or equal to 3066

The budget of sorted bytes catches it too, because the jr z costs 2 NOPs at each pair, even when it does not jump: 32 NOPs instead of 30 for two bytes. But it sees it by only 2 NOPs, whereas the guard on equal bytes shows a cost multiplied by more than 190 on 255 bytes.

What is left is the worst case, reversed bytes (bubble/13-guard):

// Reversed bytes are the slowest input: every pair swaps, each pass stops a byte earlier.
it.each([2, 16, 255])("sorts %i reversed bytes in 8.5n² + 11.5n − 19 NOPs at most", (n) => {
  const reversed = Array.from({ length: n }, (_, i) => n - 1 - i);

  expect(bubbleSort(reversed).nops).toBeLessThanOrEqual(8.5 * n * n + 11.5 * n - 19);
});

Every pair swaps, at 17 NOPs a swap: inc l 1, ld a,(hl) 2, cp e 1, jr nc 2, ld (hl),e 2, dec l 1, ld (hl),a 2, ld d,l 1, inc l 1, djnz 4. Each pass stops one byte earlier than the one before: the first compares n − 1 pairs, the last only one.

The sum gives 8.5n² + 11.5n − 19 NOPs.

Only this guard catches one broken version, and a sneaky one. It is enough to put the ld d,l after the inc l, instead of before. D then remembers the right byte of the last swap, and the next pass compares one pair too many. The array comes out sorted. On a sorted array or on equal bytes, no swap happens, D does not move, and the budgets pass. Only reversed bytes expose it:

AssertionError: expected 67 to be less than or equal to 38
AssertionError: expected 2496 to be less than or equal to 2341
AssertionError: expected 557932 to be less than or equal to 555626

Three sorts head to head

The three sorts now have their formulas, on the same three inputs:

And for 255 bytes:

On a sorted array or on equal bytes, bubble sort is the champion: for 255 bytes, it is 2.7 times faster than insertion sort, and more than 100 times faster than selection sort. A single pass is enough, at 12 NOPs a byte. On a reversed array, it comes last, with 555 626 NOPs, almost 28 frames, because a bubble moves one step for 17 NOPs, whereas LDD shifts a byte of insertion sort for 12.

On small reversed arrays, the ranking changes:

• Up to 3 bytes, bubble sort beats insertion sort. At 4 bytes, it is a perfect tie: 163 NOPs each.
• Up to 7 bytes, bubble sort beats selection sort: 478 NOPs against 485. From 8 bytes, selection sort takes the lead: 604 against 617.

In the worst case, selection takes 399 039 NOPs, insertion 395 739, and bubble 555 626. This time, the match is no draw: bubble sort costs about 40% more than the other two.

Conclusion

Knuth is not kind to bubble sort: “In short, the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems.” The worst case proves him right, but it is his own version that passed the budget, while the textbook flag missed it by 8 NOPs. The budget did not say how to do it. It only turned down what cost too much, and something better had to be found. On the CPC, bubble sort thus keeps one real strength, since an array already sorted costs it a single pass.

The routine has its restrictions:

• 1 to 255 bytes, within one 256-byte page;
• on a reversed array of 8 bytes or more, it is the slowest of the three.

The next post moves on to counting sort, which compares no bytes at all.

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 bubble branch of the z80-tdd-sorts repository. It starts from main, like the insertion branch. To replay a step:

git checkout bubble/01-red
pnpm install
pnpm test

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

Links

• The previous post: insertion sort, four versions measured
• Selection sort and its complexity
• The introduction: find_min and TDD on the CPC
• z80-tdd, the test tool
• z80-tdd-sorts, the repository of this post (branch bubble)
• RASM, the assembler by Édouard Bergé (Roudoudou)
• Perfectly accurate Z80 flags and CPC timing, Madram / Overlanders (64NOPS), the table of durations in NOPs
• Donald E. Knuth, The Art of Computer Programming, volume 3, Sorting and Searching, 2nd edition, Addison-Wesley, 1998: §5.2.2, with Algorithm B