TDD sur CPC : le tri par sélection, et ce qu'il coûte

24/10/2026Z80CPCTDDtri

Combien de temps faut-il à un CPC pour trier 255 octets ? Sur PC, on répond « O(n²) » et on passe à autre chose, mais sur CPC, on veut des NOPs. On va donc écrire un tri par sélection en Z80, test après test, jusqu’à une formule exacte de sa durée, vérifiée elle aussi par un test.

En chemin, on tombe sur deux surprises : des tests qui n’échouaient que par chance, et un pire cas qui n’est pas le tableau à l’envers.

Le point de départ est la routine find_min et ses tests, écrits dans l’article précédent, qui présente aussi la méthode.

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. Comme pour find_min, le tableau tient dans une page de 256 octets.

Le tri par sélection cherche le plus petit octet du tableau et l’échange avec le premier, qui se trouve alors à sa place. Puis il recommence sur le reste, jusqu’au dernier octet. Vous pouvez lancer l’animation ou avancer étape par étape : la flèche montre l’octet lu, la case pleine le minimum du moment, et les cases au contour coloré les octets déjà à leur place.

La complexité, en NOPs

La complexité d’un algorithme décrit la façon dont sa durée grandit avec la taille des données. Prenons find_min telle que l’article précédent l’a laissée (intro/11-green), et lançons-la sur des tableaux de plus en plus longs. Au pire, chaque octet est un nouveau minimum (octets décroissants). Au mieux, le premier octet est déjà le plus petit (octets croissants). Voici les durées mesurées, en NOPs :

Le compte se refait à la main, comme pour le budget de l’article précédent, en partant des 5 NOPs de l’entrée. Un tour où le minimum change en coûte 11 : inc l 1, cp (hl) 2, jr c 2 quand il ne saute pas, ld a,(hl) 2, djnz 4. Un tour où il ne change pas en coûte 10, car jr c saute (3 NOPs) par-dessus ld a,(hl). Avec n − 1 tours, un dernier djnz moins cher d’un NOP et le ret final, on obtient 11n − 4 NOPs au pire, et 10n − 3 au mieux.

Quand n double, la durée double : find_min est linéaire, ce que les informaticiens écrivent O(n), « proportionnel à n, à une constante près ». Le O() jette la constante, alors que sur CPC, c’est souvent elle qui compte (ici, 11 NOPs par octet).

Le tri par sélection appelle find_min sur n octets, puis sur n − 1, et ainsi de suite jusqu’à 2. La somme de ces longueurs vaut à peu près n²/2 : quand n double, la durée est multipliée par quatre. C’est du O(n²). Il reste à écrire le tri, puis à trouver la formule exacte.

Le premier test

Le code part de la fin de l’article précédent : find_min et ses six tests. Dès que selection-sort.asm existe (selection/02-green), le source principal inclut les deux routines :

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

Pour rappel, un test met des valeurs dans les registres et en mémoire, appelle la routine, puis compare le résultat à ce qu’on attend. Dans tous les tests de l’article, HL vaut #8000 et B la longueur du tableau, si bien que les tableaux de test ne montrent que les octets et le résultat attendu. Les tests appellent selection_sort, sauf deux qui appellent find_min, et leur tableau le précise.

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

Un octet, puis deux

Le premier test échoue pour la bonne raison : la routine n’existe pas encore (selection/01-red) :

Error: The Program has no label "selection_sort"

Voici le moins de code possible pour passer au vert (selection/02-green) :

selection_sort:
 ret

C’est la même triche que dans l’article précédent : la routine ne trie rien. Deux octets dans le mauvais ordre la démasquent (selection/03-red) :

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

La routine laisse les deux octets dans le mauvais ordre :

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

Ce message vient de Vitest, l’outil qui lance les tests, et non de z80-tdd, d’où les octets en décimal : 66 vaut #42, et 23 vaut #17. z80-tdd ne sait pas encore comparer une zone de mémoire à des octets attendus, et il faut donc lire le décimal. Pour deux octets, une comparaison et un échange suffisent, toujours sans boucle (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 doit dire où

À partir de trois octets, il faut échanger le minimum avec le premier octet, donc savoir où il est. Or find_min ne rend que sa valeur. Avant d’écrire la boucle, on ajoute donc un test à 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 });
});

La routine ne touche pas encore à DE :

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

Comme le tableau tient dans une page, D ne change jamais et prend la page de H dès l’entrée. Seul E suit le 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

Le nouveau test passe, mais un ancien tombe, celui du budget de 172 NOPs sur 16 octets décroissants :

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

Le budget de l’article précédent fait son travail. Le compte est vite fait : ld d,h et ld e,l ajoutent 2 NOPs à l’entrée, et ld e,l ajoute 1 NOP à chacun des 15 tours où le minimum change, soit 172 + 2 + 15 = 189. On ne voit pas de version moins chère, puisque A et l’adresse doivent changer tous les deux à chaque nouveau minimum. On relève donc le budget à 189 NOPs, en connaissance de cause, et le test dit pourquoi en commentaire :

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

La boucle

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

La version à deux octets échoue :

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

En hexadécimal, la routine a laissé #30, #42, #05, #17, #99 : elle a échangé les deux premiers octets, puis elle s’est arrêtée. Il est temps d’écrire la vraie boucle (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

Tous les tests sont maintenant verts. Il y a n − 1 passages, car le dernier octet est trié quand tous les autres le sont. find_min déplace L et vide B, d’où les push et les pop autour de l’appel. Quand le minimum est déjà en place, DE vaut HL et l’octet s’échange avec lui-même : cela ne change rien, et un test pour l’éviter coûterait des NOPs à chaque passage.

Des tests qui échouaient par chance

Un test qui passe dès son écriture doit prouver qu’il sait échouer : on casse la routine exprès, et on vérifie qu’il devient rouge. L’article précédent appelle ces tests des guards (gardes). Ici, c’est en cassant la routine qu’un trou apparaît dans les tests déjà écrits.

Oublions le dec b de l’entrée. Chaque passage demande alors à find_min un octet de trop, celui qui suit le tableau, et le tri fait un passage de plus. Les tests de tri échouent aussitôt, et celui d’un octet montre l’échange de trop :

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

Mais ils échouent seulement parce que chaque test part d’une mémoire neuve, remplie de #00. Ce zéro, plus petit que tout octet, entre dans le tableau. Avec #FF après le tableau, find_min ne le choisirait jamais, et la version cassée passerait tous les tests.

Les tests dépendaient donc d’une condition qu’ils ne disaient pas, et le guard suivant la dit tout haut, en écrivant lui-même #00 juste après le tableau (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]);
});

Il passe dès son écriture, et avec la version sans dec b, il donne l’adresse fautive, en hexadécimal cette fois :

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

Le vrai pire cas

Il reste la formule promise au début, et pour l’écrire, il faut le tableau qui fait le plus souffrir le tri. On penserait au tableau à l’envers, mais la mesure dit autre chose (durées en NOPs) :

Les octets tous égaux sont le pire cas. Avec deux octets égaux, cp (hl) ne met pas la retenue, donc find_min prend un nouveau minimum à chaque octet. Dans un tableau à l’envers, au contraire, les échanges remettent de l’ordre au fil des passages, et certains tours prennent le chemin court : 56 tours sur 120 pour 16 octets.

Voici le compte pour n octets égaux. Sur m octets, find_min coûte 12m − 3 NOPs : 7 à l’entrée, 12 par tour, 1 de moins pour le dernier djnz, 3 pour le ret. Le tri ajoute 32 NOPs autour de chaque appel : 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.

Les passages portent sur m = n, n − 1, … jusqu’à 2 octets, et la somme donne 6n² + 35n − 36 NOPs : du O(n²), avec ses constantes.

Le dernier guard fixe ce plafond pour trois longueurs (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);
});

Ce guard attrape une tentation classique : remettre inc hl dans find_min pour lever la contrainte de page. C’est 1 NOP de plus par tour de find_min, et le tri fait n(n − 1)/2 tours dans ses appels. Les trois cas tombent :

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

Le budget de find_min tombe lui aussi (expected 204 to be less than or equal to 189) : il voit le surcoût sur 16 octets. Le guard, lui, dit ce que ce surcoût coûte au tri : 32 385 NOPs de plus sur 255 octets.

Pour 255 octets, le tri prend au pire 399 039 NOPs, soit environ 20 trames de 19 968 NOPs. Voilà la réponse à la question du début : 0,4 seconde.

Conclusion

Avec z80-tdd, la complexité se mesure au NOP près, et un test la fixe. Le tri par sélection garde son O(n²), mais ses constantes sont maintenant écrites, et une optimisation future ne pourra plus les dégrader sans faire tomber un guard.

Le tri garde les limites de find_min : de 1 à 255 octets, dans une page de 256 octets. Il fait aussi un échange inutile quand le minimum est déjà en place.

Le prochain article passe au tri par insertion, avec la même recherche de son pire cas.

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 selection du dépôt z80-tdd-sorts, qui part du dernier tag de l’article précédent. Pour rejouer une étape :

git checkout selection/01-red
pnpm install
pnpm test

Sur les tags selection/*, l’option --no-lockfile n’est plus nécessaire : le premier commit de la branche corrige le lockfile que pnpm 10.34.1 ou plus refusait.

Les tests du tri sont dans src/selection-sort.test.ts, à côté de ceux de find_min. Pour installer z80-tdd dans un projet à vous, voir la section Pour essayer chez vous de l’article précédent.

Liens

• L’article précédent : find_min et l’introduction au TDD sur CPC
• z80-tdd, l’outil de test
• z80-tdd-sorts, le dépôt de cet article (branche selection)
• RASM, l’assembleur d’Édouard Bergé (Roudoudou)
• Perfectly accurate Z80 flags and CPC timing, Madram / Overlanders (64NOPS), la table des durées en NOPs