Trier des données
Je vais vous présenter différents algorithmes de tri efficaces. Chacun ayant leur utilité dans des contextes différents
Si on veut trier des données 8 bits, un bête comptage suivi d'une reconstruction fait l'affaire, par exemple :
- trier les valeurs 45,45,33,0,99,189,200,45,33,24,9,8,7,2,2,2
On va parcourir le tableau et compter chaque occurence (pour l'exemple je vais compter en 8 bits mais si on dépasse 256 valeurs à trier, il faudra passer le tableau de comptage et la reconstruction en 16 bits).
; DE=données à trier ; B=taille du tableau triComptage push de ld hl,sortBuffer : xor a ; effacer les stats .init ld (hl),a : inc l : ld (hl),a : inc l : jr nz,.init ; remplir les stats .loop ld a,(de) : inc de ld l,a : inc (hl) ; incrément le comptage djnz .loop ; reconstruire les données ex hl,de : ld e,b : pop hl .rebuild ld a,(de) : or a : jr z,.next .rebuildLoop ld (hl),e : inc hl : dec a : jr nz,.rebuildLoop .next inc e : jr nz,.rebuild ret align 256 : sortBuffer defs 256 mesDonnees defb 45,45,33,0,99,189,200,45,33,24,9,8,7,2,2,2 |
Le tri par comptage est intéressant par sa simplicité et sa complexité linéaire. Trier 10 fois plus de données est seulement 10 fois plus lent, contrairement à beaucoup d'algorithmes avec lesquels le temps explose.
Pour résumer notre exemple, voici la mémoire (j'ai dupliqué notre tableau de 16 valeurs, il est présent en #300 et #310 pour pouvoir comparer avant/après). La zone #200-#2FF correspond aux comptages.
#200 comptage #300 Référence #310 Référence triée
Trier des objets à partir d'une valeur
C'est bien gentil de trier des valeurs mais les cas d'usage sont limités. Le cas le plus courant consiste à trier des objets à partir d'un élément.
N'oublions pas que nous sommes sur une architecture légère et qu'il est coûteux de déplacer la mémoire, aussi le plus efficace va être de trier un duo contenant la valeur de tri et un index.
Nous allons trier les mêmes valeurs sauf que cette fois-ci, un index est associé (et cet index pointera vers n'importe quel type d'objet) :
| 45,0 / 45,1 / 33,2 / 0,3 / 99,4 / 189,5 / 200,6 / 45,7 / 33,8 / 24,9 / 9,10 / 8,11 / 7,12 / 2,13 / 2,14 / 2,15 |
Le comptage ne suffit pas car on perd l'information de position à la reconstruction (ici notre index). On va se créer deux tableaux pour le tri et trier au bit. Commençons par trier le plus petit bit.
; HL=données à trier ; B=nombre d'éléments bitSort push hl ld c,1 ld ix,0 ; XL=XH=0 compteurs de file ld de,file1 : exx : ld de,file2 : exx .sortBit ld a,(hl) : and c : jr z,.file0 .file1 inc c : ldi : inc c : ldi inc xh djnz .sortBit jr .rebuild .file0 ld a,(hl) : inc hl : exx : ld (de),a : inc de : exx ld a,(hl) : inc hl : exx : ld (de),a : inc de : exx inc xl djnz .sortBit .rebuild pop de ld hl,file0 |
Nos duos sont copiés dans file0 quand le bit testé vaut zéro, et dans file1 quand le bit testé vaut 1.
Quand le tri est terminé, on dépile nos deux files, l'une après l'autre pour écraser nos données d'origine. Si on n'avait qu'un seul bit à traiter, nos données seraient triées. D'abord les duo à zéro, ensuite ceux à 1.
On va ajouter de quoi tester la valeur 8 bits, à savoir boucler sur tous les bits de la valeur de tri. Assez peu de changement au code en fait :)
; HL=données à trier ; B=nombre d'éléments heapSort ld c,1 .loop push bc,hl ld ix,0 ; XL=XH=0 compteurs de file ld de,file1 : exx : ld de,file0 : exx .sortBit ld a,(hl) : and c : jr z,.file0 .file1 inc c : ldi : inc c : ldi inc xh djnz .sortBit jr .rebuild .file0 ld a,(hl) : inc hl : exx : ld (de),a : inc de : exx ld a,(hl) : inc hl : exx : ld (de),a : inc de : exx inc xl djnz .sortBit .rebuild pop de : push de ; besoin de garder une copie du HL origine ld hl,file0 |
Les duos sont bien triés comme on peut les comparer ici, avec la copie non triées et les données finales triées.