436
A Rappels algorithmiques
Procédure TriRadixMSD(tableau T, entier p,entier r,entier d)
// Précondition : T[1 . . n] est un tableau de chaînes de caractères sur
l’alphabet {0, . . . , tailleAlphabet − 1} ; La tranche T[p . . r] ne
contient que des chaînes de longueur supérieure ou égale à d.
// Postcondition : La tranche T[p . . r] est triée en considérant pour les
d-ièmes suffixes (i.e., commençant à la position d ≥ 1 dans les chaînes de
caractères) en ordre croissant pour l’ordre lexicographique.
// Variables locales : entier i, entier j,
tableau comptage[0 . .tailleAlphabet],
tableau aux[1 . . r − p + 1]
// aux est un tableau temporaire d’entiers qui stocke le résultat (il peut être
global) ; comptage est un tableau de comptage local nécessaire dans la
version présentée.
// Utilise : TriRadixMSD ;
si r > p alors
// Initialisation
pour j de 0 à tailleAlphabet faire
comptage[j] = 0
// Calcul des fréquences dans comptage dans un tableau
pour i de p à r faire
comptage[Digit(T[i], d) + 1] += 1
// Calcul des fréquences cumulées
pour j de 1 à tailleAlphabet - 1 faire
comptage[j] += comptage[j - 1]
// Affectation dans un nouveau tableau en calculant grâce à comptage
pour chaque élément du tableau d’entrée T son rang dans le tableau trié
pour i de p à r faire
aux[comptage[Digit(T[i], d)]+1] = T[i]
comptage[Digit(T[i], d)] += 1
// Copie du tableau trié aux dans T
pour i de p à r faire
T[i] = aux[i - p + 1]
// appels récursifs pour chaque symbole de l’alphabet
TriRadixMSD(T, p, p + comptage[0] - 1, d + 1)
pour j de 0 à tailleAlphabet - 2 faire
TriRadixMSD(T, p + comptage[j],
p + comptage[j + 1] - 1, d + 1)