TDD sur CPC : le tri par comptage, 256 compteurs et pas une comparaison

24/10/2026Z80CPCTDDtri

Les trois tris des articles précédents font la même chose : ils comparent des octets, deux par deux. Le tri de cet article ne compare rien du tout. C’est un algorithme connu, le tri par comptage : on compte les octets, puis on les réécrit dans l’ordre. Simple, mais combien de NOPs ?

La réponse se construit en Z80, test après test, et c’est le compte des NOPs qui choisira entre deux boucles de copie. Pour finir, les quatre tris passent sur les mêmes entrées, côte à côte.

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 trois tris précédents, et le tableau tient toujours dans une page de 256 octets.

Un octet ne prend que 256 valeurs. On réserve donc 256 compteurs, un par valeur. On parcourt le tableau une fois, et chaque octet ajoute 1 à son compteur. Ensuite, on parcourt les compteurs dans l’ordre, de #00 à #FF, et on réécrit chaque valeur autant de fois qu’on l’a comptée. Le tableau sort trié, sans une seule comparaison entre deux octets.

Lancez l’animation, ou avancez étape par étape. La première rangée est le tableau, et la flèche montre l’octet compté. La seconde rangée montre les compteurs des valeurs du tableau, et « … » les compteurs vides entre elles. La case pleine montre le compteur lu ou modifié, et les cases au contour coloré les octets déjà réécrits. L’animation montre la version finale de l’article : chaque copie retire 1 au compteur, qui revient à zéro avec la dernière. La section sur le décompte explique pourquoi.

Le coût change de forme : il n’a plus de terme en n², mais deux termes, n pour le comptage et la réécriture, et 256 pour le parcours des compteurs, quelle que soit la taille du tableau. Sur un petit tableau, ces 256 compteurs coûtent cher. Sur un grand, ils ne comptent presque plus. Les tests mesureront où passe la frontière.

La table des compteurs

Avec 255 octets au plus, un compteur ne dépasse jamais 255 : un octet suffit. Les compteurs vivent dans une table counts de 256 octets, alignée sur une page. H pointe alors sur la table, et L choisit le compteur à lui seul : ld l,a puis inc (hl), et le compteur de la valeur A gagne 1.

Il faut aussi remettre la table à zéro. On pourrait l’effacer au début de chaque appel, mais on fait autrement : la table est à zéro en entrée, et la routine la rend à zéro en sortie. Le defs 256 de l’assembleur la crée à zéro, et chaque appel la laisse comme il l’a trouvée, ce qu’un test vérifiera plus loin.

Le premier test

Comme le tri par insertion et le tri à bulles, le tri par comptage 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 "counting-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.

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 counting_sort on `bytes`, written at ARRAY.
function countingSort(bytes: number[]) {
  return program.run("counting_sort", {
    registers: { hl: ARRAY, b: bytes.length },
    memory: [{ at: ARRAY, bytes }],
  });
}

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

Un octet, puis deux

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

it("swaps two bytes in the wrong order", () => {
  expect(countingSort([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. Avec les tris précédents, le code vert de cette étape comparait deux octets. Ici, on compte dès le deuxième test. Le code vert compte chaque octet, puis parcourt les compteurs et réécrit chaque valeur comptée, une fois. Il remet aussi chaque compteur à zéro au passage (counting/04-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 E never carries into D.
; counts must hold zeros on entry, and holds zeros again on exit.
counting_sort:
 ex de,hl       ; DE: the array
 push de
 ld hl,counts
.count:
 ld a,(de)
 ld l,a
 inc (hl)       ; one more copy of this byte
 inc e
 djnz .count
 pop de         ; DE: back to the first byte
.scan:          ; L runs over the counts, up to #FF
 ld a,(hl)
 or a
 jr z,.next
 ld (hl),0      ; the count goes back to zero for the next call
 ld a,l
 ld (de),a
 inc e
.next:
 inc l
 jr nz,.scan
 ret

 align 256
counts:         ; one count for each byte value: L indexes it alone
 defs 256

DE pointe sur le tableau, HL sur la table. Le parcours s’arrête quand inc l repasse à zéro, après le compteur de #FF. Ce code a un défaut que les tests ne voient pas encore, et on y reviendra.

Les doublons

Une valeur peut apparaître plusieurs fois. Le test suivant en met deux paires (counting/05-red) :

it("keeps every copy of a repeated byte", () => {
  expect(countingSort([0x42, 0x17, 0x42, 0x17]).memory(ARRAY, 4)).toEqual([
    0x17, 0x17, 0x42, 0x42,
  ]);
});

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

En hexadécimal, la routine a laissé #17, #42, #42, #17. #17 et #42 sont écrits une fois chacun, et la fin du tableau garde ses anciens octets. Le compteur sert maintenant de longueur : B le reçoit, et une boucle écrit la valeur B fois (counting/06-green) :

.scan:          ; L runs over the counts, up to #FF
 ld a,(hl)
 or a
 jr z,.next
 ld b,a         ; B: the copies of this byte to write
 ld (hl),0      ; the count goes back to zero for the next call
 ld a,l
.copy:
 ld (de),a
 inc e
 djnz .copy
.next:
 inc l
 jr nz,.scan
 ret

B est libre, puisque la boucle de comptage l’a laissé à zéro.

Un parcours qui part de travers

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

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

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

En hexadécimal, la routine a laissé #99, #30, #05, #17, #99. Seul le premier octet a changé, et il vaut #99, parce que le parcours ne part pas de #00. Après la boucle de comptage, L garde le dernier octet compté, ici #99. Le parcours commence donc au compteur de #99, écrit #99, puis lit des compteurs vides jusqu’à #FF et s’arrête. Les compteurs de #05 à #42 n’ont jamais été lus.

Le défaut était là depuis 04-green. Les tests d’avant passaient par chance : dans #42, #17 comme dans #42, #17, #42, #17, le dernier octet est aussi le plus petit. Le parcours partait de #17, et ne ratait rien.

Le correctif tient en une instruction. Après djnz, B vaut zéro, et ld l,b met L à #00 pour 1 NOP, là où ld l,0 en coûte 2 (counting/08-green) :

 pop de         ; DE: back to the first byte
 ld l,b         ; L: #00, as DJNZ leaves B at zero
.scan:          ; L runs over the 256 counts

Les deux bouts de la table

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 vise les deux bouts de la table, les compteurs de #00 et de #FF (counting/09-guard) :

// #00 and #FF sit in the first and last counts: the scan must read all 256.
it("sorts #FF and #00, the two ends of the counts", () => {
  expect(countingSort([0xff, 0x42, 0x00]).memory(ARRAY, 3)).toEqual([0x00, 0x42, 0xff]);
});

La version cassée qu’il vise arrête le parcours un compteur trop tôt. Il suffit d’un ld a,l et d’un inc a avant le jr nz,.scan : la boucle s’arrête dès que L atteint #FF, avant de lire son compteur. Aucun autre test ne contient #FF, et seul ce guard tombe :

AssertionError: expected [ +0, 66, +0 ] to deeply equal [ +0, 66, 255 ]

Vitest écrit le zéro +0. En hexadécimal, le guard attendait #00, #42, #FF et trouve #00, #42, #00 : le #FF n’a jamais été réécrit.

Le tri à bulles avait un guard pour une paire de trop, qui lisait l’octet après le tableau. Ici, la version qui compte un octet de trop, avec un inc b en entrée, ne passe aucun des tests existants. Elle compte le #00 qui suit le tableau, puis réécrit un octet de trop, et les tests existants suffisent à l’attraper.

Une table rendue propre

Le contrat promet une table à zéro en sortie. Le guard suivant le vérifie : seul le tableau doit changer (counting/10-guard) :

// A count of 2 or more must also go back to zero: the next call counts on top of it.
it("changes only the array, even with repeated bytes", () => {
  expect(countingSort([0x42, 0x17, 0x42, 0x17])).toChangeOnly({ address: ARRAY, length: 4 });
});

Le tableau a des octets répétés parce que la version cassée qu’il vise met dec (hl) à la place de ld (hl),0. Un compteur de 1 revient bien à zéro, mais un compteur de 2 reste à 1. Le tri reste juste, car B garde le bon nombre de copies, et tous les autres tests passent. Le guard, lui, voit les restes :

Error: Memory changed outside #8000-#8003:
  #4117  #00 -> #01
  #4142  #00 -> #01

La table est en #4100, juste après le code du programme. Les compteurs de #17 et #42 y sont restés à 1. Le prochain appel compterait par-dessus, et écrirait un #17 et un #42 de trop.

Décompter dans la table

Tout est vert, et le code peut maigrir. La boucle de copie compte avec B, puis le compteur est remis à zéro. Il est plus simple de décompter directement dans la table : dec (hl) arrive à zéro avec la dernière copie, et la table est propre sans rien de plus. ld b,a et ld (hl),0 disparaissent (counting/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 never carries into D.
; counts must hold zeros on entry, and holds zeros again on exit.
counting_sort:
 ex de,hl       ; DE: the array
 push de
 ld hl,counts
.count:
 ld a,(de)
 ld l,a
 inc (hl)       ; one more copy of this byte
 inc e
 djnz .count
 pop de         ; DE: back to the first byte
 ld l,b         ; L: #00, as DJNZ leaves B at zero
.scan:          ; L runs over the 256 counts
 ld a,(hl)
 or a
 jr z,.next
 ld a,l
.copy:
 ld (de),a
 inc e
 dec (hl)       ; the count reaches zero with the last copy, ready for the next call
 jr nz,.copy
.next:
 inc l
 jr nz,.scan
 ret

 align 256
counts:         ; one count for each byte value: L indexes it alone
 defs 256

Mais une copie coûte maintenant 9 NOPs au lieu de 7 : dec (hl) et jr nz prennent 6 NOPs, là où djnz en prenait 4. Le bilan dépend donc de l’entrée, et il faut compter.

Le compte à la main

Le compte dépend de n, la longueur du tableau, et de d, le nombre de valeurs différentes qu’il contient. Chaque boucle coûte un NOP de moins à son dernier tour, quand son saut ne saute pas.

Le parcours des 256 compteurs pèse 2 559 NOPs, quoi qu’il arrive. La somme donne 2 573 + 20n − d NOPs.

Le même compte sur la boucle djnz de 08-green donne 2 573 + 18n + 3d NOPs. La version qui décompte gagne quand d dépasse n/2. Le pire cas compte plus :

Le pire cas baisse d’un NOP par octet, et c’est ce qui a décidé.

Les budgets

Les deux derniers tests sont des guards de budget : un nombre de NOPs à ne pas dépasser. D’abord le pire cas, les octets égaux (counting/12-guard) :

// Equal bytes are the slowest input: one count, then n turns of the copy loop.
it.each([2, 16, 255])("sorts %i equal bytes in 20n + 2572 NOPs at most", (n) => {
  const equal = Array.from({ length: n }, () => 0x42);

  expect(countingSort(equal).nops).toBeLessThanOrEqual(20 * n + 2572);
});

La version cassée qu’il vise met le ld a,l dans la boucle de copie, après le label. Le tri reste juste, mais chaque copie coûte un NOP de plus, et chaque compteur plein un NOP de moins. Sur des octets tous différents, chaque compteur vaut 1, et la version cassée coûte exactement autant que la bonne. Les octets égaux, eux, font n copies d’un seul compteur :

AssertionError: expected 2613 to be less than or equal to 2612
AssertionError: expected 2907 to be less than or equal to 2892
AssertionError: expected 7926 to be less than or equal to 7672

Puis les octets triés et à l’envers, ensemble (counting/13-guard) :

// The order changes nothing: sorted and reversed bytes both mean n counts of 1.
it.each([2, 16, 255])("sorts %i sorted or reversed bytes in 19n + 2573 NOPs at most", (n) => {
  const sorted = Array.from({ length: n }, (_, i) => i);
  const reversed = [...sorted].reverse();

  expect(countingSort(sorted).nops).toBeLessThanOrEqual(19 * n + 2573);
  expect(countingSort(reversed).nops).toBeLessThanOrEqual(19 * n + 2573);
});

Pour la première fois de la série, l’ordre ne change rien. Trié ou à l’envers, chaque valeur a un compteur de 1, et la routine fait exactement le même travail. La version cassée que ce guard attrape est la boucle djnz de 08-green, à 21n + 2 573. Elle passe le budget des octets égaux, où elle est moins chère, et tombe ici :

AssertionError: expected 2615 to be less than or equal to 2611
AssertionError: expected 2909 to be less than or equal to 2877
AssertionError: expected 7928 to be less than or equal to 7418

Quatre tris face à face

Voici les formules des quatre tris, sur les trois mêmes entrées :

Et pour 255 octets :

Le graphique montre les octets à l’envers. En haut, de 2 à 40 octets, à l’échelle linéaire. En bas, de 2 à 255 octets, à l’échelle logarithmique :

Sur de petits tableaux, le comptage est le plus lent, et de loin : 2 611 NOPs pour deux octets, quand les trois autres en prennent moins de 60. Mais sa droite monte de 19 NOPs par octet, et les paraboles finissent par la croiser. À l’envers, il passe devant les bulles dès 18 octets, puis devant la sélection et l’insertion dès 21 octets. À 255 octets, son pire cas, 7 672 NOPs, tient en 38 % d’une trame de 19 968 NOPs. Face au pire cas de chacun, c’est 52 fois moins que la sélection et l’insertion, et 72 fois moins que les bulles.

Le comptage ne gagne pas partout, pourtant. Sur un tableau déjà trié ou d’octets égaux, les bulles restent devant à toutes les tailles : 3 066 NOPs pour 255 octets, contre 7 418. L’insertion aussi résiste, jusqu’à 185 octets triés et 199 octets égaux. Le comptage, lui, ne sait pas que le tableau est déjà trié : il paie ses 256 compteurs à chaque appel.

Conclusion

Le tri par comptage ne compare rien, et il y gagne un coût linéaire, le même pour toutes les entrées à un NOP par octet près. Les tests ont trouvé un parcours qui partait de travers, puis ont tenu la table propre d’un appel à l’autre. Le compte des NOPs, lui, a choisi la boucle de copie, pour un NOP par octet gagné sur le pire cas.

Ce tri a pourtant ses limites :

• de 1 à 255 octets, dans une page de 256 octets ;
• un prix d’entrée fixe : 2 559 NOPs pour parcourir la table, et 256 octets de mémoire pour la loger ;
• sur un tableau trié ou d’octets égaux, le tri à bulles reste plus rapide à toutes les tailles ;
• des octets seuls : avec une clé et ses données, la réécriture perd le lien entre les deux, car elle sait combien de #42 écrire, pas lesquels.

Le prochain article passe au tri par base, le radix sort, sur des clés de 16 bits. Le comptage y revient, sous une forme stable, comme passe interne.

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 counting du dépôt z80-tdd-sorts. Elle part de main, comme la branche bubble. Pour rejouer une étape :

git checkout counting/01-red
pnpm install
pnpm test

Les tests du tri sont dans src/counting-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 à bulles, le drapeau ou la borne de Knuth
• Le tri par insertion et le tri par sélection
• 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 counting)
• RASM, l’assembleur d’Édouard Bergé (Roudoudou)
• Perfectly accurate Z80 flags and CPC timing, Madram / Overlanders (64NOPS), la table des durées en NOPs