TDD sur CPC : le tri à bulles, le drapeau ou la borne de Knuth

24/10/2026Z80CPCTDDtri

Le tri par insertion de l’article précédent profite de l’ordre qu’il trouve dans le tableau. Le tri à bulles est le plus célèbre des tris simples, et aussi le plus moqué. Sur un Z80, mérite-t-il sa réputation ?

On va le vérifier en l’écrivant en Z80, test après test. Un test de budget y départage plusieurs versions, dont celle des manuels, puis les trois tris se retrouvent face à face.

La méthode est celle de l’article sur find_min, à lire d’abord si le TDD vous est nouveau.

Ce que fait la routine

HL pointe sur le tableau, B contient sa longueur (de 1 à 255), et la routine trie le tableau sur place, du plus petit au plus grand. C’est le contrat des deux tris précédents, et le tableau tient toujours dans une page de 256 octets.

On parcourt le tableau, et on compare chaque octet à son voisin de droite. Si le voisin est plus petit, les deux échangent leur place. Le plus grand octet vu jusqu’ici avance ainsi jusqu’au bout du tableau, comme une bulle qui remonte : c’est la bulle. Une passe met donc au moins un octet à sa place, le dernier. On recommence jusqu’à ce que le tableau soit trié.

Lancez l’animation, ou avancez étape par étape : la case pleine montre la bulle, la flèche l’octet comparé à la bulle, et les cases au contour coloré les octets déjà à leur place, au bout du tableau. L’animation montre la version finale de l’article : une passe s’arrête là où la précédente a fait son dernier échange. La section sur le budget explique pourquoi.

Sur un tableau déjà trié, la première passe n’échange rien. Sur un tableau à l’envers, chaque comparaison échange. Les tests mesureront ces deux cas plus loin.

Le premier test

Comme le tri par insertion, le tri à bulles n’a pas besoin de find_min. Le code repart de zéro, et le source principal n’inclut que la nouvelle routine :

 org #4000
 include "bubble-sort.asm"

Dans les tests de cet article, HL vaut #8000 et B la longueur du tableau. Les tableaux de test ne montrent donc que les octets et le résultat attendu. Ce sont les mêmes tableaux de 1, 2 et 5 octets que pour les deux tris précédents, pour comparer les trois tris à la fin.

Un tableau d’un octet est déjà trié. Le premier test vérifie seulement que la routine ne touche pas à la mémoire :

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

Un octet, puis deux

Les premières étapes suivent celles des deux tris précédents. Le test d’un octet échoue faute de label (bubble/01-red), et un simple ret le fait passer (bubble/02-green). Deux octets dans le mauvais ordre démasquent cette triche (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 affiche les octets en décimal : 66 vaut #42, et 23 vaut #17. Le code vert compare les deux octets, et les échange s’ils sont dans le mauvais ordre. Un détail compte déjà : l’octet de gauche, la bulle, reste dans 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

Une passe

Le test suivant place le plus grand octet en tête d’une suite triée. Une seule passe doit l’amener au bout (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 ]

En hexadécimal, la routine a laissé #05, #42, #17, #30 : seule la première paire a bougé. La passe devient une boucle sur les paires, et B les compte. Si l’octet suivant est plus petit que la bulle, on écrit la bulle à sa droite et l’octet à sa gauche : la bulle avance d’une place. Sinon, la bulle s’arrête, et l’octet suivant devient la bulle (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

La bulle reste dans E parce qu’elle est déjà lue : sans E, chaque paire relirait ses deux octets en mémoire.

Toutes les passes

Le test suivant trie cinq octets mélangés (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 ]

En hexadécimal, la routine a laissé #30, #05, #17, #42, #99. La passe a bien poussé #42 contre #99, mais le début reste en désordre. Il faut répéter la passe, une fois par paire. C compte les passes, et la pile garde B et HL pour que chaque passe reparte du premier octet (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

Tous les tests sont verts, avec le tri à bulles des manuels : n − 1 passes complètes, quoi qu’il arrive.

Une paire de trop

Le tri par insertion reculait dans le tableau, et il a fallu un mur avant le premier octet. Le tri à bulles avance par inc l, et son dec l revient seulement sur l’octet gauche de la paire : rien ne lit avant le tableau. Le danger est de l’autre côté : avec une paire de trop, la passe tire dans le tableau l’octet qui le suit.

Le test suivant passe dès son écriture : c’est un guard. Un guard doit prouver qu’il sait échouer. On casse donc la routine exprès, et on vérifie qu’il devient rouge. Ce guard place un octet plus petit juste après le tableau (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]);
});

La version cassée qu’il vise ajoute un inc b après le ld c,b : chaque passe compare une paire de trop. Le guard la voit :

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

Mais les trois tests de tri tombent aussi :

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 écrit le zéro +0. En hexadécimal, le premier test attendait #17, #42 et trouve #17, #00. Dans les trois tableaux, le #00 qui suit le tableau a pris la place du plus grand octet, poussé dehors.

Dans l’article précédent, le #00 de la mémoire neuve cachait un bug. Ici, il le trahit : c’est le plus petit octet possible, et la paire de trop le fait entrer dans le tableau. Les anciens tests attrapent donc la version cassée, mais par chance, alors que le guard écrit ce #00 noir sur blanc.

Le budget refuse le drapeau

Tout est vert, mais la routine fait toutes ses passes, même sur un tableau déjà trié. Le test suivant fixe un budget, un nombre de NOPs à ne pas dépasser, pour 2, 16 et 255 octets triés (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);
});

Contrairement à ceux de l’insertion, ce budget n’est pas un guard : il échoue, et c’est lui qui fait avancer le code. Il vise une seule passe sans échange, puis la sortie. Le code de 08-green en est loin :

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

Pour 255 octets déjà triés, la routine fait 254 passes sans un seul échange, et prend 779 024 NOPs, soit 39 trames de 19 968 NOPs.

La réponse classique, c’est un drapeau : si une passe n’échange rien, le tableau est trié, et on s’arrête. Trois retouches suffisent :

• un ld d,0 en début de passe ;
• un ld d,1 à chaque échange ;
• après le pop bc, un dec d suivi d’un ret nz.

Tous les tests de tri restent verts, mais le budget tombe encore :

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

Le budget est raté de 8 NOPs, quelle que soit la taille. Le drapeau arrête bien le tri après une passe, mais il s’ajoute au compteur de passes, sans le remplacer. Le ld c,b, le push bc et le pop bc restent, et le ld d,0 et le dec d s’y ajoutent.

Donald Knuth a une meilleure idée, l’algorithme B de The Art of Computer Programming (volume 3, §5.2.2). On retient la position du dernier échange. Tous les octets après lui sont à leur place, donc la passe suivante s’arrête là. Si une passe n’échange rien, la borne reste au premier octet, et le tri s’arrête. Un seul registre remplace à la fois le compteur de passes et le drapeau (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 garde L sur l’octet gauche du dernier échange. Après la passe, sub l donne le nombre de paires avant lui : c’est la longueur de la passe suivante. S’il vaut zéro, ret z termine. C a disparu, et la pile ne garde plus que HL.

Comme pour l’insertion, le compte se refait à la main. Une paire sans échange coûte 12 NOPs : inc l 1, ld a,(hl) 2, cp e 1, jr nc 3, ld e,a 1, djnz 4.

La somme donne 12n + 6 NOPs. Le budget tombe juste, sans un NOP de marge.

Les guards

Les deux derniers tests passent dès leur écriture. D’abord les octets égaux, le pire cas de la sélection (bubble/12-guard). Ici, comme pour l’insertion, c’est aussi le meilleur cas : jr nc arrête la bulle dès que l’octet suivant n’est pas plus petit, donc la bulle ne dépasse jamais un octet égal. Le guard reprend le budget des octets triés :

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

La version cassée qu’il vise échange aussi les octets égaux : un jr z,$+4 avant le jr nc saute vers l’échange. Le tri reste correct, mais 255 octets égaux coûtent alors 588 011 NOPs, plus que 255 octets à l’envers avec la bonne 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

Le budget des octets triés l’attrape aussi, car le jr z coûte 2 NOPs à chaque paire, même quand il ne saute pas : 32 NOPs au lieu de 30 pour deux octets. Mais il la voit à 2 NOPs près, alors que le guard des octets égaux montre un coût multiplié par plus de 190 sur 255 octets.

Il reste le pire cas, les octets à l’envers (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);
});

Chaque paire échange, à 17 NOPs l’échange : 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. Chaque passe s’arrête un octet plus tôt que la précédente : la première compare n − 1 paires, la dernière une seule.

La somme donne 8,5n² + 11,5n − 19 NOPs.

Seul ce guard attrape une version cassée, et elle est sournoise. Il suffit de poser le ld d,l après le inc l, au lieu d’avant. D retient alors l’octet droit du dernier échange, et la passe suivante compare une paire de trop. Le tableau sort trié. Sur un tableau trié ou d’octets égaux, aucun échange n’a lieu, D ne bouge pas, et les budgets passent. Seuls les octets à l’envers la démasquent :

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

Trois tris face à face

Les trois tris ont maintenant leurs formules, sur les trois mêmes entrées :

Et pour 255 octets :

Sur un tableau trié ou d’octets égaux, le tri à bulles est le champion : pour 255 octets, il est 2,7 fois plus rapide que l’insertion, et plus de 100 fois plus rapide que la sélection. Il lui suffit d’une passe, à 12 NOPs l’octet. Sur un tableau à l’envers, c’est le dernier, avec 555 626 NOPs, près de 28 trames, car une bulle avance d’un pas pour 17 NOPs, alors que LDD décale un octet de l’insertion pour 12.

Sur de petits tableaux à l’envers, le classement change :

• Jusqu’à 3 octets, les bulles battent l’insertion. À 4 octets, c’est l’égalité parfaite : 163 NOPs chacun.
• Jusqu’à 7 octets, les bulles battent la sélection : 478 NOPs contre 485. Dès 8 octets, la sélection passe devant : 604 contre 617.

Dans le pire cas, la sélection prend 399 039 NOPs, l’insertion 395 739, et les bulles 555 626. Cette fois, le match n’est plus nul : les bulles coûtent environ 40 % de plus que les deux autres.

Conclusion

Knuth n’est pas tendre avec le tri à bulles : « En bref, le tri à bulles semble n’avoir rien pour lui, sauf un nom accrocheur et le fait qu’il mène à des problèmes théoriques intéressants. » Le pire cas lui donne raison, mais c’est sa propre version qui a passé le budget, alors que le drapeau des manuels ratait de 8 NOPs. Le budget n’a pas dit comment faire. Il a seulement refusé ce qui coûtait trop, et il a fallu chercher mieux. Sur CPC, le tri à bulles garde ainsi un vrai point fort, puisqu’un tableau déjà trié lui coûte une seule passe.

La routine garde des limites :

• de 1 à 255 octets, dans une page de 256 octets ;
• sur un tableau à l’envers de 8 octets ou plus, c’est la plus lente des trois.

Le prochain article passe au tri par comptage, qui ne compare aucun octet.

Pour essayer chez vous

Il vous faut Node.js 24 ou plus, pnpm, et RASM v3.3.1 dans le PATH. Les étapes de cet article sont sur la branche bubble du dépôt z80-tdd-sorts. Elle part de main, comme la branche insertion. Pour rejouer une étape :

git checkout bubble/01-red
pnpm install
pnpm test

Les tests du tri sont dans src/bubble-sort.test.ts. Pour installer z80-tdd dans un projet à vous, voir la section Pour essayer chez vous de l’article sur find_min.

Liens

• L’article précédent : le tri par insertion, quatre versions mesurées
• Le tri par sélection et sa complexité
• L’introduction : find_min et le TDD sur CPC
• z80-tdd, l’outil de test
• z80-tdd-sorts, le dépôt de cet article (branche bubble)
• RASM, l’assembleur d’Édouard Bergé (Roudoudou)
• Perfectly accurate Z80 flags and CPC timing, Madram / Overlanders (64NOPS), la table des durées en NOPs
• Donald E. Knuth, The Art of Computer Programming, volume 3, Sorting and Searching, 2e édition, Addison-Wesley, 1998 : le §5.2.2, avec l’algorithme B