A Rappels algorithmiques
435
Par exemple sur le tableau T d’entiers de [0 . . 4] (K = 5) de taille 9
i 1 2 3 4 5 6 7 8 9
T[i] 0 1 1 2 3 0 4 4 0
,
le tableau comptage avec les fréquences cumulées sera
i
0 1 2 3 4 5
comptage[i] 0 3 5 6 7 9
.
On peut interpréter ce tableau de la manière suivante : la première clé 0 sera au rang
comptage[0] + 1 = 1 dans le tableau trié, la première clé 1 au rang comptage[1] +
1 = 4, la première clé 2 au rang comptage[2] + 1 = 5, etc. Le tableau comptage
est mis à jour après chaque affectation d’une clé dans le tableau trié afin de pouvoir
calculer la prochaine place libre pour une clé de même valeur.
Nous revenons maintenant au tri radix avec un alphabet non forcément binaire.
La fonction de tri suivante est appelée pour un tableau T[1 . . n] de chaînes
de caractères avec TriRadixMSD(T, 1, n, 1). Elle utilise le tri par comptage en
examinant les positions successives dans les chaînes de caractères.
435
Par exemple sur le tableau T d’entiers de [0 . . 4] (K = 5) de taille 9
i 1 2 3 4 5 6 7 8 9
T[i] 0 1 1 2 3 0 4 4 0
,
le tableau comptage avec les fréquences cumulées sera
i
0 1 2 3 4 5
comptage[i] 0 3 5 6 7 9
.
On peut interpréter ce tableau de la manière suivante : la première clé 0 sera au rang
comptage[0] + 1 = 1 dans le tableau trié, la première clé 1 au rang comptage[1] +
1 = 4, la première clé 2 au rang comptage[2] + 1 = 5, etc. Le tableau comptage
est mis à jour après chaque affectation d’une clé dans le tableau trié afin de pouvoir
calculer la prochaine place libre pour une clé de même valeur.
Nous revenons maintenant au tri radix avec un alphabet non forcément binaire.
La fonction de tri suivante est appelée pour un tableau T[1 . . n] de chaînes
de caractères avec TriRadixMSD(T, 1, n, 1). Elle utilise le tri par comptage en
examinant les positions successives dans les chaînes de caractères.