A Rappels algorithmiques
437
Nous pouvons aussi examiner les bits de la droite vers la gauche (approche
bottom-up ou LSD Least significant Digit) mais cela nécessite de considérer des
clés de même longueur. Dans l’implémentation suivante, nous utilisons le tri par
comptage. Une caractéristique importante du tri par comptage, la stabilité, est
nécessaire ici : les positions relatives de deux clés égales dans le tableau d’entrée
sont laissées inchangées dans le tableau de sortie. Si nous n’avions pas cette
propriété, nous pourrions casser ce que nous avions fait dans une passe précédente
de l’algorithme.
Procédure TriRadixLSD(tableau T, entier n)
// Précondition : T[1 . . n] est un tableau de chaînes de caractères de longueur
longueur sur l’alphabet {0, . . . , tailleAlphabet − 1}.
// Postcondition : Retourne le tableau T[1 . . n] trié en ordre croissant pour
l’ordre lexicographique.
// Variables locales : entier i, entier j,
tableau comptage[0 . .tailleAlphabet], tableau aux[1 . . n]
// 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.
pour d de longueur - 1 à 1 faire
pour j de 0 à tailleAlphabet faire
comptage[j] = 0
pour i de 1 à n faire
comptage[Digit(T[i], d) + 1] += 1
pour j de 1 à tailleAlphabet - 1 faire
comptage[j] += comptage[j - 1]
pour i de 1 à n faire
aux[comptage[Digit(T[i], d)] + 1] = T[i]
comptage[Digit(T[i], d)] += 1
pour i de 1 à n faire
T[i] = aux[i]
Ce tri effectue n × longueur comparaisons de symboles.
A.6 Tris par comparaisons
A.6.1 Tri rapide
Nous rappelons le principe de base du tri rapide, qui est de structurer l’ensemble des
clés par rapport à une clé spéciale, utilisée comme pivot :
437
Nous pouvons aussi examiner les bits de la droite vers la gauche (approche
bottom-up ou LSD Least significant Digit) mais cela nécessite de considérer des
clés de même longueur. Dans l’implémentation suivante, nous utilisons le tri par
comptage. Une caractéristique importante du tri par comptage, la stabilité, est
nécessaire ici : les positions relatives de deux clés égales dans le tableau d’entrée
sont laissées inchangées dans le tableau de sortie. Si nous n’avions pas cette
propriété, nous pourrions casser ce que nous avions fait dans une passe précédente
de l’algorithme.
Procédure TriRadixLSD(tableau T, entier n)
// Précondition : T[1 . . n] est un tableau de chaînes de caractères de longueur
longueur sur l’alphabet {0, . . . , tailleAlphabet − 1}.
// Postcondition : Retourne le tableau T[1 . . n] trié en ordre croissant pour
l’ordre lexicographique.
// Variables locales : entier i, entier j,
tableau comptage[0 . .tailleAlphabet], tableau aux[1 . . n]
// 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.
pour d de longueur - 1 à 1 faire
pour j de 0 à tailleAlphabet faire
comptage[j] = 0
pour i de 1 à n faire
comptage[Digit(T[i], d) + 1] += 1
pour j de 1 à tailleAlphabet - 1 faire
comptage[j] += comptage[j - 1]
pour i de 1 à n faire
aux[comptage[Digit(T[i], d)] + 1] = T[i]
comptage[Digit(T[i], d)] += 1
pour i de 1 à n faire
T[i] = aux[i]
Ce tri effectue n × longueur comparaisons de symboles.
A.6 Tris par comparaisons
A.6.1 Tri rapide
Nous rappelons le principe de base du tri rapide, qui est de structurer l’ensemble des
clés par rapport à une clé spéciale, utilisée comme pivot :