TDD sur CPC : le tri par insertion, quatre versions au NOP près

24/10/2026Z80CPCTDDtri

Le tri par sélection de l’article précédent ne tient pas compte de l’ordre des octets : même sur un tableau déjà trié, il cherche le minimum à chaque passage. Le tri par insertion, lui, profite de l’ordre qu’il trouve. Mais que coûte-t-il quand il n’y en a aucun ?

Pour le savoir, on l’écrit en Z80, test après test, on essaie quatre façons de décaler les octets, mesurées au NOP près, et on finit par mettre les deux tris 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 de selection_sort, et le tableau tient toujours dans une page de 256 octets.

Le tri par insertion est le tri du joueur de cartes : on prend les cartes une à une, et on glisse chacune à sa place parmi celles déjà en main. Le tableau se coupe en deux : à gauche, une suite triée, à droite, les octets qui restent. Au départ, la suite triée ne contient que le premier octet. À chaque passage, on prend l’octet qui la suit : la clé. Tant que l’octet à gauche de la clé est plus grand qu’elle, il se décale d’une place vers la droite. Puis la clé s’écrit dans la place libérée.

Lancez l’animation, ou avancez étape par étape : les cases au contour coloré forment la suite triée, la case pleine montre la clé, et la flèche l’octet comparé à la clé. Le Z80 garde la clé dans A pendant les décalages, et ne l’écrit qu’à la fin. L’animation la montre déjà à la place où elle s’écrira.

Sur un tableau déjà trié, chaque clé s’arrête tout de suite : une comparaison par octet, et c’est tout. Sur un tableau à l’envers, chaque clé traverse toute la suite triée. Le meilleur et le pire cas se devinent déjà, et les tests les mesureront.

Le premier test

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

 org #4000
 include "insertion-sort.asm"

Dans les tests de cet article, HL vaut #8000 et B la longueur du tableau, sauf dans un test, qui le précise. Les tableaux de test ne montrent donc que les octets et le résultat attendu. Ce sont les mêmes octets que pour selection_sort, pour comparer les deux 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 insertion_sort on `bytes`, written at ARRAY.
function insertionSort(bytes: number[]) {
  return program.run("insertion_sort", {
    registers: { hl: ARRAY, b: bytes.length },
    memory: [{ at: ARRAY, bytes }],
  });
}

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

Un octet, puis deux

Les premières étapes suivent celles de la sélection. Le test d’un octet échoue faute de label (insertion/01-red), et un simple ret le fait passer (insertion/02-green). Deux octets dans le mauvais ordre démasquent cette triche (insertion/03-red) :

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

Le simple ret laisse les deux octets tels quels :

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 diffère déjà de celui de la sélection. La clé, c’est le deuxième octet, et on la compare à l’octet avant elle (insertion/04-green) :

insertion_sort:
 dec b
 ret z
 inc l
 ld a,(hl)      ; the key: the byte to insert
 dec l
 cp (hl)
 ret nc         ; the key is not below the byte before it
 ld c,(hl)      ; move that byte one place right, and the key into its place
 ld (hl),a
 inc l
 ld (hl),c
 ret

Une seule clé

Le test suivant place une clé tout devant une suite déjà triée (insertion/05-red) :

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

La version à deux octets ne voit pas la dernière clé :

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

En hexadécimal, la routine a laissé #17, #30, #42, #05, car elle ne regarde que les deux premiers octets. Pour ce test, une seule clé suffit, la dernière, qui recule pas à pas vers le début du tableau, toujours sans boucle externe (insertion/06-green) :

insertion_sort:
 dec b
 ret z
 ld a,l
 add a,b
 ld l,a         ; HL: the last byte
 ld a,(hl)      ; the key: the byte to insert
.shift:
 dec l
 cp (hl)
 jr nc,.place   ; the key is not below this byte
 ld c,(hl)      ; move this byte one place right
 inc l
 ld (hl),c
 dec l
 jr .shift
.place:
 inc l
 ld (hl),a
 ret

Cette boucle n’a pas de borne : elle s’arrête sur le premier octet qui n’est pas plus grand que la clé. Rien ne l’oblige à s’arrêter au début du tableau, et on y reviendra plus loin.

La boucle externe

Le test suivant trie cinq octets mélangés (insertion/07-red) :

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

Avec une seule clé, la routine échoue sur ce tableau :

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

En hexadécimal, la routine a laissé #42, #30, #05, #17, #99, puisque la dernière clé, #99, était déjà à sa place. La boucle externe insère maintenant chaque octet à son tour. E garde la position de la clé, pour que le passage suivant reparte de là (insertion/08-green) :

insertion_sort:
 dec b          ; one pass for each byte but the first
 ret z
.next:
 inc l          ; HL: the next byte to insert
 ld e,l         ; the next pass starts from there
 ld a,(hl)      ; the key: the byte to insert
.shift:
 dec l
 cp (hl)
 jr nc,.place   ; the key is not below this byte
 ld c,(hl)      ; move this byte one place right
 inc l
 ld (hl),c
 dec l
 jr .shift
.place:
 inc l
 ld (hl),a
 ld l,e
 djnz .next
 ret

Tous les tests sont verts, mais la boucle interne n’a toujours pas de borne.

Le mur avant le tableau

Quand la clé est plus petite que tous les octets de la suite triée, elle dépasse le premier octet, et la boucle continue de lire avant le tableau. Pour le prouver, il suffit d’y mettre un octet plus grand, #FF : le code sans borne va le décaler dans le tableau.

Le premier essai plaçait le tableau en #8000 et le #FF en #7FFF. Le test est passé alors qu’il devait échouer, parce que dec l ne touche pas H : depuis #8000, il ne recule pas en #7FFF, mais en #80FF, au bout de la même page. Or la mémoire neuve de z80-tdd vaut #00 partout, et ce zéro, plus petit que toute clé, arrête la boucle. C’est encore un test qui passait par chance, comme dans l’article sur la sélection.

Le test place donc le tableau un octet plus loin, en #8001, juste après le #FF (insertion/09-red). C’est le seul test où HL ne vaut pas #8000 :

it("ignores a larger byte right before the array", () => {
  // Fresh memory holds #00 next to ARRAY. The array starts one byte into the
  // page, after the #FF, so a step back by DEC L or DEC HL reads the #FF.
  const run = program.run("insertion_sort", {
    registers: { hl: ARRAY + 1, b: 5 },
    memory: [{ at: ARRAY, bytes: [0xff, 0x42, 0x30, 0x05, 0x17, 0x99] }],
  });

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

Cette fois, il échoue pour la bonne raison. Dès le premier passage, la clé #30 pousse le #FF dans le tableau, et prend sa place, hors du tableau. Au passage suivant, la clé #05 l’en chasse :

Error: Memory changed outside #8001-#8005:
  #8000  #FF -> #05

La borne la plus simple, c’est un compteur. D compte les octets de la suite triée, et E en reçoit une copie à chaque passage : la clé ne peut pas dépasser plus de E octets. Comme E est pris, la position de la clé passe sur la pile (insertion/10-green) :

insertion_sort:
 dec b          ; one pass for each byte but the first
 ret z
 ld d,0
.next:
 inc d          ; D: the bytes of the sorted run
 inc l          ; HL: the next byte to insert
 push hl        ; the next pass starts from there
 ld e,d         ; E: the bytes the key can still move past
 ld a,(hl)      ; the key: the byte to insert
.shift:
 dec l
 cp (hl)
 jr nc,.place   ; the key is not below this byte
 ld c,(hl)      ; move this byte one place right
 inc l
 ld (hl),c
 dec l
 dec e
 jr nz,.shift
 dec l          ; the key goes first: .place steps back onto the first byte
.place:
 inc l
 ld (hl),a
 pop hl
 djnz .next
 ret

Le dec l après la boucle est une petite astuce : .place avance d’un octet avant d’écrire, donc on recule d’un octet de plus quand la clé va en tête.

Quatre façons de décaler

Tout est vert, et la routine est correcte, mais rien ne dit encore qu’elle est rapide. Avant de fixer des budgets, on essaie donc trois autres boucles internes :

• La sentinelle, tirée d’Algorithms in C de Robert Sedgewick (Program 6.3). Une première passe amène le plus petit octet en tête du tableau. Aucune clé ne peut aller plus loin que lui, et la boucle interne n’a plus besoin de borne.
• Les échanges, tirés d’Algorithms (4e édition, Sedgewick et Wayne). La clé recule en s’échangeant avec l’octet avant elle, au lieu de le décaler.
• LDD, l’idée du Z80. Cette instruction copie l’octet de (HL) vers (DE), recule HL et DE, et décrémente BC. Le flag P/V dit si BC n’est pas encore à zéro : BC devient la borne.

z80-tdd a mesuré les quatre versions sur des octets triés et sur des octets à l’envers. Pour chacune, le compte des NOPs donne une formule exacte :

Les formules de la sentinelle valent à partir de 3 octets. Aucune version ne gagne partout :

• Les échanges sont les plus rapides sur un tableau trié, et les plus lents à l’envers : un échange écrit deux octets, un décalage un seul.
• La sentinelle paie sa première passe dans tous les cas, et sa boucle interne ne gagne qu’un NOP par octet décalé sur le compteur E.
• LDD est la plus lente à démarrer : à chaque passage, il faut préparer DE et BC, et sauver BC. Mais elle décale un octet en 12 NOPs : cp (hl) 2, jr nc 2, ldd 5, jp pe 3. Le compteur E en demande 15. Sur 255 octets à l’envers, LDD prend 395 739 NOPs, et le compteur E 490 608.

LDD gagne le pire cas, et sur un tableau trié elle ne perd que 8 NOPs par passage sur le compteur E. C’est elle que garde la routine. Le nettoyage (refactor) remplace la boucle interne sans toucher un seul test (insertion/11-refactor) :

; Sorts in place, smallest first, the array at HL, B bytes long (1 to 255).
; The array stays within one 256-byte page: INC E keeps D on the page of H.
insertion_sort:
 dec b          ; one pass for each byte but the first
 ret z
 ld c,0
.next:
 inc c          ; C: the bytes of the sorted run
 push bc
 ld d,h         ; DE: the next byte to insert, then the hole it leaves
 ld e,l
 inc e
 push de        ; the next pass starts from there
 ld a,(de)      ; the key: the byte to insert
 ld b,0         ; BC: the bytes the key can still move past
.shift:
 cp (hl)        ; HL: the byte before the hole
 jr nc,.place   ; the key is not below this byte
 ldd            ; move this byte into the hole; P/V: BC is not 0
 jp pe,.shift
.place:
 ld (de),a
 pop hl         ; HL: the last byte of the sorted run
 pop bc
 djnz .next
 ret

jr ne connaît pas la condition pe, d’où le jp. Et l’astuce du dec l disparaît : quelle que soit la sortie de la boucle, DE pointe sur la place libérée.

Les guards

Place aux tests qui passent dès leur écriture, les guards. Chacun doit prouver qu’il sait échouer : on casse la routine exprès, et on vérifie qu’il devient rouge.

Le premier reprend celui de la sélection : un octet plus petit juste après le tableau (insertion/12-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("insertion_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]);
});

Sans le dec b de l’entrée, le tri fait un passage de trop, et insère l’octet qui suit le tableau. Les anciens tests tombent eux aussi, mais seulement grâce au #00 de la mémoire neuve. Avec #FF après le tableau, la version cassée les passerait tous. Le guard le dit tout haut :

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

Le meilleur cas

Les trois guards suivants fixent les budgets, pour 2, 16 et 255 octets. D’abord le meilleur cas, les octets triés (insertion/13-guard) :

// Sorted bytes are the fastest input: each key stops at the byte before it.
it.each([2, 16, 255])("sorts %i sorted bytes in 33n − 26 NOPs at most", (n) => {
  const sorted = Array.from({ length: n }, (_, i) => i);

  expect(insertionSort(sorted).nops).toBeLessThanOrEqual(33 * n - 26);
});

Le compte se refait à la main. Un passage où la clé ne bouge pas coûte 33 NOPs : inc c 1, push bc 4, ld d,h 1, ld e,l 1, inc e 1, push de 4, ld a,(de) 2, ld b,0 2, cp (hl) 2, jr nc 3, ld (de),a 2, pop hl 3, pop bc 3, djnz 4.

La somme donne 33n − 26 NOPs. Ce guard attrape la sentinelle, qui paie sa première passe :

AssertionError: expected 47 to be less than or equal to 40
AssertionError: expected 566 to be less than or equal to 502
AssertionError: expected 9409 to be less than or equal to 8389

Les octets égaux

Ensuite les octets égaux, le pire cas de la sélection (insertion/14-guard). Ici, c’est aussi le meilleur cas : cp (hl) met la retenue seulement si la clé est strictement plus petite, donc une clé ne dépasse jamais un octet égal. Le guard reprend le budget des octets triés :

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

  expect(insertionSort(equal).nops).toBeLessThanOrEqual(33 * n - 26);
});

La version cassée qu’il vise compare avec ≤ au lieu de < : un jr z avant le jr nc fait passer la clé devant les octets égaux. Les octets égaux deviennent alors presque aussi lents que les octets à l’envers :

AssertionError: expected 48 to be less than or equal to 40
AssertionError: expected 1987 to be less than or equal to 502
AssertionError: expected 428124 to be less than or equal to 8389

Ce guard n’est pas le seul à l’attraper. Le jr z coûte 2 NOPs à chaque comparaison, même quand il ne saute pas, et le guard des octets triés tombe aussi : 42 NOPs au lieu de 40 pour deux octets. Mais lui la voit de justesse, alors que le guard des octets égaux montre l’ampleur des dégâts.

Le pire cas

Il reste le pire cas, les octets à l’envers (insertion/15-guard) :

// Reversed bytes are the slowest input: each key moves past the whole sorted run.
it.each([2, 16, 255])("sorts %i reversed bytes in 6n² + 22n − 21 NOPs at most", (n) => {
  const reversed = Array.from({ length: n }, (_, i) => n - 1 - i);

  expect(insertionSort(reversed).nops).toBeLessThanOrEqual(6 * n * n + 22 * n - 21);
});

Au k-ième passage, la clé dépasse les k octets de la suite triée. Hors de la boucle interne, le passage coûte 28 NOPs : les 33 du meilleur cas, moins le cp (hl) et le jr nc qui sortaient de la boucle. Chaque octet décalé ajoute 12 NOPs.

La somme donne 6n² + 22n − 21 NOPs. Ce guard attrape les échanges :

AssertionError: expected 2272 to be less than or equal to 1867
AssertionError: expected 554362 to be less than or equal to 395739

Il attrape aussi le compteur E :

AssertionError: expected 2092 to be less than or equal to 1867
AssertionError: expected 490608 to be less than or equal to 395739

Pour deux octets, les deux versions passent sous le plafond : l’écart se creuse avec n. La sentinelle, déjà prise par le guard des octets triés, tombe ici aussi : 1 991 NOPs au lieu de 1 867 pour 16 octets.

Sélection contre insertion

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

Et pour 255 octets :

Sur un tableau trié ou d’octets égaux, l’insertion est linéaire, et 40 à 48 fois plus rapide que la sélection. Sur un tableau à l’envers, c’est l’inverse, à partir d’une certaine taille. Jusqu’à 26 octets, l’insertion reste devant (4 607 NOPs contre 4 618), mais dès 27 octets, la sélection gagne (4 945 contre 4 947). L’insertion déplace en effet chaque octet d’un pas à la fois, à 12 NOPs le pas, alors que la sélection cherche longtemps, mais n’écrit qu’un échange par passage.

Il reste à comparer les pires cas : 399 039 NOPs pour la sélection, sur des octets égaux, et 395 739 pour l’insertion, sur des octets à l’envers. L’écart fait moins d’un pour cent, et on peut parler de match nul, avec environ 20 trames de 19 968 NOPs de chaque côté pour trier 255 octets.

Conclusion

Les mesures de z80-tdd ont choisi la version LDD, et trois guards gardent ce choix : une modification qui ralentit l’un des trois cas mesurés fait tomber un test. Sur un tableau trié, l’insertion est 40 fois plus rapide que la sélection, et dans le pire cas, les deux tris font jeu égal.

La routine garde des limites :

• de 1 à 255 octets, dans une page de 256 octets ;
• sur un tableau à l’envers de plus de 26 octets, la sélection est plus rapide.

Le prochain article passe au tri à bulles.

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 insertion du dépôt z80-tdd-sorts. Elle part de main, et non de selection, puisque le tri par insertion n’a pas besoin de find_min. Pour rejouer une étape :

git checkout insertion/01-red
pnpm install
pnpm test

Les tests du tri sont dans src/insertion-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 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 insertion)
• RASM, l’assembleur d’Édouard Bergé (Roudoudou)
• Perfectly accurate Z80 flags and CPC timing, Madram / Overlanders (64NOPS), la table des durées en NOPs
• Robert Sedgewick, Algorithms in C, 3e édition, Addison-Wesley, 1998 : le Program 6.3, avec sa sentinelle
• Algorithms, 4e édition, Robert Sedgewick et Kevin Wayne : le tri par insertion par échanges