Le tri par dénombrement (counting sort en anglais) est l’un des algorithmes de tri le plus rapide, et pourtant il est loin d'être compliqué, même s'il a quelques restrictions et défauts. Le tri s'exécute en un temps linéaire, mais uniquement sur des nombres entiers. La particularité du tri est qu'il est la base d'autres algorithmes de tri en temps linéaires, permettant de s'adapter aux besoins en temps et en mémoire.
Le principe est simple, on parcourt le tableau et on compte le nombre de fois que chaque élément apparaît. Une fois qu’on a le tableau des effectifs E (avec E[i] le nombre de fois où i apparaît dans le tableau), on peut le parcourir dans le sens croissant (pour un tri croissant), ou décroissant (pour un tri décroissant) et placer dans le tableau trié E[i] fois l’élément i (avec i allant de l’élément minimum du tableau jusqu’à l’élément maximum).
Voici un tableau d’entier que l’on souhaite trier dans l’ordre croissant en utilisant le tri par dénombrement : 8, 6, 1, 3, 8, 1, 1.
La première étape est de créer notre tableau des effectifs E, la deuxième est simplement de le parcourir et de recopier dans le tableau trié les valeurs :
i | E[i] | Action | Tableau trié |
---|---|---|---|
0 | 0 | on ne fait rien | |
1 | 3 | on ajoute trois fois 1 | 1 1 1 |
2 | 0 | on ne fait rien | 1 1 1 |
3 | 1 | on ajoute une fois 3 | 1 1 1 3 |
4 | 0 | on ne fait rien | 1 1 1 3 |
5 | 0 | on ne fait rien | 1 1 1 3 |
6 | 1 | on ajoute une fois 6 | 1 1 1 3 6 |
7 | 0 | on ne fait rien | 1 1 1 3 6 |
8 | 2 | on ajoute deux fois 8 | 1 1 1 3 6 8 8 |
On a atteint le maximum de notre tableau des effectifs E, notre tableau est donc trié :
1, 1, 1, 3, 6, 8, 8.
Cependant cet algorithme possède des défauts (même s'il s’exécute en temps linéaire) :
Cet algorithme est donc très efficace, mais il faut savoir faire un choix entre rapidité et stockage (en plus de ne pas pouvoir l'utiliser sur autres choses que des entiers).
Le pseudo-code de l’algorithme :
triDénombrement :
Chercher l'élément maximum du tableau
Créer un tableau E de taille Max + 1, initialisé à 0
Pour chaque élément du tableau
Incrémenter E[Tableau[i]]
Pour chaque élément de E
Recopier E[i] fois le nombre i dans le tableau trié
La complexité en temps de cet algorithme se calcule assez facilement. En effet, les seules opérations que l'on effectue dans notre fonction se font en temps linéaire. L'initialisation du tableau des effectifs se fait en \(O(N)\) (avec \(N\) la taille du tableau en entrée), et la copie des éléments dans notre tableau trié en \(O(M)\) (avec \(M\) correspondant à Max
).
La complexité finale de notre algorithme est donc \(O(N + M)\), soit une complexité en temps linéaire.
L'implémentation en C du tri par dénombrement :
#include <stdio.h>
#include <stdlib.h>
#define TAILLE_MAX 1000
int tableau[TAILLE_MAX];
int taille;
void triDenombrement(void)
{
int iTab, iEffectif;
int max;
int *effectif;
max = -42;
for(iTab = 0; iTab < taille; ++iTab)
if(tableau[iTab] > max)
max = tableau[iTab];
effectif = calloc(max + 1, sizeof(int));
for(iTab = 0; iTab < taille; ++iTab)
++effectif[tableau[iTab]];
for(iEffectif = 0, iTab = 0; iEffectif <= max; ++iEffectif) {
int iCopie;
for(iCopie = 0; iCopie < effectif[iEffectif]; ++iCopie) {
tableau[iTab] = iEffectif;
++iTab;
}
}
free(effectif);
}
int main(void)
{
int iTab;
scanf("%d\n", &taille);
for(iTab = 0; iTab < taille; ++iTab)
scanf("%d ", &tableau[iTab]);
triDenombrement();
for(iTab = 0; iTab < taille; ++iTab)
printf("%d ", tableau[iTab]);
printf("\n");
return 0;
}
J'utilise la fonction calloc lors de l'allocation afin d'avoir mon tableau directement initialisé à 0.
Notre tableau en entrée :
7
8 6 1 3 8 1 1
La sortie obtenue :
1 1 1 3 6 8 8
Le tri par dénombrement est donc un algorithme de tri assez restrictif (il ne travaille qu'avec des nombres entiers), et doit obliger des compromis de mémoire pour avoir une complexité en temps linéaire. Cependant, quand on connait l'entrée, on peut utiliser cet algorithme afin d'avoir un temps d'exécution très rapide, mais on peut aussi changer le fonctionnement de ce tri afin d'améliorer la complexité en mémoire, sans trop impacter la complexité en temps, et c'est ce que fait le tri par base qui est un autre algorithme en temps linéaire inspiré du tri par dénombrement. On le retrouve aussi dans le tri par paquets qui permet de faire des améliorations de manières générales en temps et en mémoire à ce dernier.