require("../global.php"); entete(); ?>
Si vous avez des questions concernant le present document, n'hesitez pas a m'envoyer un mail, ou a me parler sur IRC sur #demofr
Le Byte sort est un algorithme inspire tout droit du Radix sort, mais il a 2 enormes avantages : il est facile a coder, et il est tres rapide. Facile a coder, nous allons le voir, puisque son algo est tres simple. Tres rapide, puisque c'est un tri en N, et non en N Log N.
On va donc travailler en 3 etapes :
On le voit donc, il n'y a pas de comparaisons! Juste des positions... Cela fait que chacune des trois etapes se code en quelques lignes d'assembleur.
Pour faire ce tri, on a donc besoin des ingredients suivants :
Un bouquet garni.
Un processeur.
250g de beurre pour 8 personnes.
Plus :
Un tableau qui contient les donnees.
Un tableau qui contient les adresses.
Un tableau qui contiendra les donnees triees.
Pour les programmeurs PC en mode 32 bits, on pourrait dire :
Tableau de 1 a N de Structures <= Tableau non Trie, de N faces Numero de Face : Entier 32 bits Valeur du Z : Entier 32 bits Tableau de 0 a 255 de <= Tableau pour les positions Nombre : Entier 32 bits Tableau de 1 a N de <= Tableau Trie de N faces Numero de Face
<--- 32 bits ---> _______________ | | | | | | 1 | 2 | 3 | 4 | |___|___|___|___|
Nous verrons au dernier chapitre comment faire en moins de passes...(patience)
Bien, maintenant que nous savons que nous allons trier en 4 passes, voyons chacune des 3 etapes qui composent notre tri :
Pour i=0 a 255 faire Tab2[i]=0;
Nous allons ensuite parcourir les cases de notre tableau 1 (celui a trier) une par une. Pour chaque case, on va recuperer la valeur. Ensuite, comme vu plus haut, nous allons indiquer dans le tableau 2, que cette valeur a ete vue une fois de plus. La boucle est donc :
Pour i=0 a n-1 faire val=octet(Tab1[i].Z); /* On recupere la coordonnee. */ Tab2[val]=Tab2[val]+1;
A la fin de cette premiere etape, le tableau 2 contient le nombre de fois ou on a vu chaque octet.
Exemple :
Soit le tableau 1 :
indice 0 1 2 3 4 5 6 7 ------------------------ valeur 2 4 6 3 2 4 5 1
Le tableau 2 correspondant (ou tout du moins son debut) sera :
indice 0 1 2 3 4 5 6 7 8 ------------------------ valeur 0 1 2 1 2 1 1 0 0
position=0 Pour i=0 a 255 faire increment=Tab2[i] Tab2[i]=position position=position+increment
Donc, si on applique cette boucle a l'exemple precedent, on trouve:
indice 0 1 2 3 4 5 6 7 8 --------------------------------- valeur 0 0 1 3 4 6 7 8 8
Qu'est-ce que cela veut dire ??? Et bien tout simplement que l'emplacement
de depart des donnees dont la valeur est 1 sera la case 0. Ou que l'emplacement
de depart des donnees dont la valeur est 6 sera la case 7.
C'est magique! C'est Fantastique! (envoyez vos dons a Phar, C.C.P 148691738)
Bien, il nous reste a regler un dernier point de detail (mineur), le tri de nos donnees :
2 remarques :
Tout cela donne l'algo suivant :
Pour i=0 a N-1 faire : val=octet(Tab1[i].Z); /* on recupere la clef de tri. */ pos=tab2[val]; /* on en deduit la position. */ tab2[val]=tab2[val]+1; tab3[pos]=Tab1[i].Numero_de_face /* on place la donnee a la bonne pos*/
Et si, une fois encore, on reprend l'exemple, on avait :
Tableau 1 = indice 0 1 2 3 4 5 6 7 ------------------------ valeur 2 4 6 3 2 4 5 1 Tableau 2 = indice 0 1 2 3 4 5 6 7 8 --------------------------------- valeur 0 0 1 3 4 6 7 8 8 Donc, Tableau 3= indice 0 1 2 3 4 5 6 7 -------------------------------- valeur 7 0 4 3 1 5 6 2
Et on voit le resultat :
On a un fabuleux tableau trie! (sisi, verifiez!! il est trie!)
Donc, on vient de trier un tableau en 200 lignes de texte, mais sans aucune comparaison
Donc, passes 1 et 3 : Tab1 => Tab3 2 4 : Tab3 => Tab1 (pour ne pas consommer trop de memoire)
Revoyons l'algo au complet :
A chaque Passe, octet(x), donne l'octet de x que l'on souhaite trier.
/* Etape I */ Pour i=0 a n-1 faire val=octet(Tab1[i].Z); /* On recupere la coordonnee. */ Tab2[val]=Tab2[val]+1; /* Etape II */ position=0 Pour i=0 a 255 faire increment=Tab2[i] Tab2[i]=position position=position+increment /* Etape III */ Pour i=0 a n-1 faire : val=octet(Tab1[i].Z); pos=tab2[val]; /* on en deduit la position. */ tab2[val]=tab2[val]+1; tab3[pos]=Tab1[i].Numero_de_face /* on place la donnee a la bonne pos */
 
C'est un pur bonheur... Roudoudou en a fait une implementation, et celle-ci fait 84 lignes... Mais ce n'est pas a moi de vous expliquer comment coder ce tri en ASM...
Je vais neanmoins donner quelques tips :
Voila, c'est fini maintenant. J'espere que vous avez a peu pres compris. Et si vous avez des remarques, n'hesitez pas : un mail, ou venez sur #demofr!
- Phar / Flower Corp.
PiedDePage(); ?>