Tri Radix
Principe
Le tri Radix s'appuie sur la représentation binaire des éléments à trier.
- On sépare le tableau à trier en deux sous-tableaux
L'un ne contient que les éléments dont le bit de poids faible vaut 0
L'autre ne contient que les éléments dont le bit de poids faible vaut 1
- On met bout à bout le sous-tableau 0, puis le sous-tableau 1
- On répète les étapes ci-dessus pour le 2ème bit, puis le 3ème (du moins au plus significatif), jusqu'à avoir parcouru tous les bits significatifs.
Algorithme
Créer les 2 sous-tableaux
Pour chaque bit (du moins significatif vers le plus significatif)
- Pour chaque élément du tableau (du premier vers le dernier)
- Isoler la valeur du bit concerné
- Tester la valeur du bit et copier l'élément dans le sous-tableau adéquat
- Pour chaque sous-tableau (du plus bas vers le plus haut)
- Pour chaque élément du sous tableau (du premier vers le dernier)
- Copier l'élément dans le tableau d'origine
Supprimer les sous-tableaux
Exemple
Tableau à trier : [7,5,1,9,2]
On parcourt le tableau dans l'ordre croissant , et on place le chiffre correspondant dans le sous-tableau adéquat.
On reconstitue ensuite le tableau d'origine, à partir du Tableau 0, puis du tableau 1, en respectant l'ordre d'origine
Tableau
à trier |
Binaire |
|
Bit 0 |
|
Bit 1 |
| Tableau 0 |
Tableau 1 |
Tableau 0+1 |
Tableau 0 |
Tableau 1 |
Tableau
0+1 |
| 7 |
0111 |
001 0 |
011 1 |
0010 |
01 0 1 |
00 1 0 |
0101 |
| 5 |
0101 |
|
010 1 |
0111 |
00 0 1 |
01 1 1 |
0001 |
| 1 |
0001 |
|
000 1 |
0101 |
10 0 1 |
|
1001 |
| 9 |
1001 |
|
100 1 |
0001 |
|
|
0010 |
| 2 |
0010 |
|
|
1001 |
|
|
0111 |
| Bit 2 |
|
Bit 3 |
Tableau
trié |
Tableau
0 |
Tableau
1 |
Tableau
0+1 |
Tableau 0 |
Tableau
1 |
Tableau
0+1 |
| 0 0 01 |
0 1 01 |
0001 |
0 001 |
1 001 |
0001 |
1 |
| 1 0 01 |
0 1 11 |
1001 |
0 010 |
|
0010 |
2 |
| 0 0 10 |
|
0010 |
0 101 |
|
0101 |
5 |
| |
|
0101 |
0 111 |
|
0111 |
7 |
| |
|
0111 |
|
|
1001 |
9 |
Exemple de programme en Visual Basic
Remarques
- L'utilisation de la représentation binaire est bien adaptée à un langage de bas niveau (type Assembleur ou C), car il suffit d'effectuer un ET logique pour savoir dans quel sous-tableau ranger le nombre :
BIT2 = 2 (soit 10 en binaire)
IF 10 AND BIT2 .THEN..donnera un résultat vrai (10 donne 1010 en binaire)
IF 9 AND BIT2 .THEN..donnera un résultat faux (9 donne 1001 en binaire)
- On peut effectuer d'autres type de découpe selon le type de donnée à trier ; par exemple pour trier des nombres entiers, on peut créer 10 sous-tableaux (0 à 9), ou 26 sous-tableaux pour trier des textes.
On peut aussi effectuer le tri sur la représentation hexadécimale, etc ...
- On remarquera que les éléments du tableau à trier ne sont pas comparés entre eux, ce qui est inhabituel. Cette méthode de tri reprend en fait le principe adopté autrefois avec les trieuses de cartes perforées, ou la machine effectuait un tri sur une colonne à la fois.
Utilisation
Ce tri est assez performant avec les nombres entiers et les caractères ; ses performances sont relativement indépendantes de la répartition initiale des valeurs.
Son gros inconvénient est de nécessiter un doublement du tableau à trier (espace mémoire).
Retour à la table des matières des tris
Dernière mise à jour de cette page : 12/8/2007