A Rappels algorithmiques
433
A.5.6 Tri radix
Dans cette section les positions dans les chaînes de caractères sont indexés à partir
de 1 : pour un mot w de taille n, nous avons w = w[1 . . n].
Nous présentons d’abord la procédure de tri radix la plus élémentaire, qui utilise
une représentation binaire des clés. Elle est basée sur une logique de partitionnement
similaire au tri rapide (voir plus loin) mais utilise la valeur d’un bit pour partitionner
au lieu d’un pivot. Les bits sont examinés de la gauche vers la droite (approche
appelée parfois top-down ou MSD most significant digit) en partant de la position
1. La fonction de tri suivante est appelée pour un tableau T[1 . . n] de chaînes de
caractères avec TriRadixBin(T, 1, n, 1).
Procédure TriRadixBin(tableau T, entier p,entier r,entier d)
// Précondition : T est un tableau de chaînes de caractères ; d est un entier
supérieur ou égal à 1.
// Postcondition : La tranche T[p . . r] du tableau T est triée en ordre
croissant pour l’ordre lexicographique en considérant les d-ièmes suffixes
(les suffixes commençant à la position d).
// La procédure prend en argument les limites du sous-tableau courant p et r
et l’indice (profondeur) du bit courant d pour la comparaison.
// Variables locales : entier i, entier j, booléen fini
// Utilise : échanger, TriRadixBin, Digit
si (r > p) alors
i = p
j = r
fini = Faux
tant que non fini faire
tant que (Digit(s[i], d) == 1) et (i < j) faire
i = i + 1
tant que (Digit(s[j], d) == 0) et (i < j) faire
j = j - 1
échanger(s[i], s[j])
fini = (i ≥ j)
si Digit(s[r], d) == 0 alors
j = j + 1
// pour le cas (exceptionnel) où tous les symboles examinés ont été
‘0’
TriRadixBin(p, j - 1, d + 1)
TriRadixBin(j, r, d + 1)
La méthode est généralisable à un alphabet non binaire et devient très similaire à une autre méthode de tri appelée en anglais « bucket sort » [156, 231].
L’algorithme utilise comme routine un algorithme de tri par comptage. Le principe
de l’algorithme de tri par comptage consiste à faire un premier passage sur
433
A.5.6 Tri radix
Dans cette section les positions dans les chaînes de caractères sont indexés à partir
de 1 : pour un mot w de taille n, nous avons w = w[1 . . n].
Nous présentons d’abord la procédure de tri radix la plus élémentaire, qui utilise
une représentation binaire des clés. Elle est basée sur une logique de partitionnement
similaire au tri rapide (voir plus loin) mais utilise la valeur d’un bit pour partitionner
au lieu d’un pivot. Les bits sont examinés de la gauche vers la droite (approche
appelée parfois top-down ou MSD most significant digit) en partant de la position
1. La fonction de tri suivante est appelée pour un tableau T[1 . . n] de chaînes de
caractères avec TriRadixBin(T, 1, n, 1).
Procédure TriRadixBin(tableau T, entier p,entier r,entier d)
// Précondition : T est un tableau de chaînes de caractères ; d est un entier
supérieur ou égal à 1.
// Postcondition : La tranche T[p . . r] du tableau T est triée en ordre
croissant pour l’ordre lexicographique en considérant les d-ièmes suffixes
(les suffixes commençant à la position d).
// La procédure prend en argument les limites du sous-tableau courant p et r
et l’indice (profondeur) du bit courant d pour la comparaison.
// Variables locales : entier i, entier j, booléen fini
// Utilise : échanger, TriRadixBin, Digit
si (r > p) alors
i = p
j = r
fini = Faux
tant que non fini faire
tant que (Digit(s[i], d) == 1) et (i < j) faire
i = i + 1
tant que (Digit(s[j], d) == 0) et (i < j) faire
j = j - 1
échanger(s[i], s[j])
fini = (i ≥ j)
si Digit(s[r], d) == 0 alors
j = j + 1
// pour le cas (exceptionnel) où tous les symboles examinés ont été
‘0’
TriRadixBin(p, j - 1, d + 1)
TriRadixBin(j, r, d + 1)
La méthode est généralisable à un alphabet non binaire et devient très similaire à une autre méthode de tri appelée en anglais « bucket sort » [156, 231].
L’algorithme utilise comme routine un algorithme de tri par comptage. Le principe
de l’algorithme de tri par comptage consiste à faire un premier passage sur