434
A Rappels algorithmiques
le tableau pour compter le nombre d’occurrences de chaque symbole, puis à
refaire un deuxième passage pour mettre les éléments à leur place en fonction
du comptage effectué. Cette technique dans son implémentation la plus naturelle
suppose d’allouer un autre tableau pour trier les données car le tri n’est pas effectué
en place. Nous donnons ci-après le code permettant de trier un tableau T [1 . . n]
d’entiers pris dans l’intervalle [0 . . K − 1] (avec K fixé). La complexité est O(n × K)
en temps et O(n + K) en espace. Considérant que K est fixé, cet algorithme trie donc
en temps (et en espace) linéaire.
Cette méthode de tri, bien que simple, est plus subtile qu’il y paraît. La version
ci-après a la propriété d’être stable : deux clés de même valeur seront dans le
même ordre dans le tableau d’entrée et de sortie. Cette propriété est nécessaire dans
différents contextes (comme par exemple dans la version LSD du tri radix) décrite
plus loin. Nous employons aussi par commodité la notation usuelle en informatique
« a += b » qui signifie « a = a + b ».
Procédure TriComptage(tableau T, entier n)
// Précondition : T[1 . . n] est un tableau d’entiers de [0 . . K − 1], n est la
taille du tableau.
// Postcondition : Retourne le tableau T trié en ordre croissant.
// Variables locales : entier i, entier j, tableau aux[1 . . n],
tableau comptage[0 . .K]
// 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.
// Initialisation
pour j de 0 à K faire
comptage[j] = 0
// Calcul des fréquences dans comptage dans un tableau en décalant
« astucieusement » les indices de 1
pour i de 1 à n faire
comptage[T[i] + 1] += 1
// Calcul des fréquences cumulées
pour j de 1 à K - 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 1 à n faire
aux[comptage[T[i]]+1] = T[i]
comptage[T[i]] += 1
// Copie du tableau trié aux dans T
pour i de 1 à n faire
T[i] = aux[i - 1]
A Rappels algorithmiques
le tableau pour compter le nombre d’occurrences de chaque symbole, puis à
refaire un deuxième passage pour mettre les éléments à leur place en fonction
du comptage effectué. Cette technique dans son implémentation la plus naturelle
suppose d’allouer un autre tableau pour trier les données car le tri n’est pas effectué
en place. Nous donnons ci-après le code permettant de trier un tableau T [1 . . n]
d’entiers pris dans l’intervalle [0 . . K − 1] (avec K fixé). La complexité est O(n × K)
en temps et O(n + K) en espace. Considérant que K est fixé, cet algorithme trie donc
en temps (et en espace) linéaire.
Cette méthode de tri, bien que simple, est plus subtile qu’il y paraît. La version
ci-après a la propriété d’être stable : deux clés de même valeur seront dans le
même ordre dans le tableau d’entrée et de sortie. Cette propriété est nécessaire dans
différents contextes (comme par exemple dans la version LSD du tri radix) décrite
plus loin. Nous employons aussi par commodité la notation usuelle en informatique
« a += b » qui signifie « a = a + b ».
Procédure TriComptage(tableau T, entier n)
// Précondition : T[1 . . n] est un tableau d’entiers de [0 . . K − 1], n est la
taille du tableau.
// Postcondition : Retourne le tableau T trié en ordre croissant.
// Variables locales : entier i, entier j, tableau aux[1 . . n],
tableau comptage[0 . .K]
// 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.
// Initialisation
pour j de 0 à K faire
comptage[j] = 0
// Calcul des fréquences dans comptage dans un tableau en décalant
« astucieusement » les indices de 1
pour i de 1 à n faire
comptage[T[i] + 1] += 1
// Calcul des fréquences cumulées
pour j de 1 à K - 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 1 à n faire
aux[comptage[T[i]]+1] = T[i]
comptage[T[i]] += 1
// Copie du tableau trié aux dans T
pour i de 1 à n faire
T[i] = aux[i - 1]