Dans cet article, nous allons aborder l'algorithme de tri par seau. Le tri par seau ou tri par compartiment encore appelé Bucket Sort en anglais est un algorithme de tri dans lequel les éléments du tableau d'entrée sont répartis dans des compartiments. Suite à la répartition des éléments, les compartiments sont triés individuellement par un autre algorithme de tri ou par appel récursif à lui-même. Enfin, après avoir trié tous les compartiments, les éléments de ces compartiments sont combinés pour former un tableau trié.
L'étape de combinaison est triviale (contrairement au tri par fusion). Il suffit de copier les éléments de chaque compartiment dans le tableau d'origine ou de joindre la tête de chaque compartiment avec la queue du compartiment précédent (dans le cas de listes chaînées).
Les avantages du tri par seau sont les suivants :
- Le tri par seau réduit le nombre de comparaisons.
- Il est asymptotiquement rapide en raison de la distribution uniforme des éléments.
Les limites du tri par seau sont les suivantes :
- Il peut ou pas être un algorithme de tri stable.
- Le coût de l'algorithme du tri par seau augmente lorsque la taille du tableau devient grande.
- Ce n'est pas un algorithme de tri en place, car un espace supplémentaire est nécessaire pour trier les compartiments.
Le tri par seau reste quelque peu abstrait dans la mise en œuvre.
La complexité de l'algorithme du tri par seau dans le meilleur des cas et dans le cas moyen est de O(n + k) ; et dans le pire des cas, la complexité de l'algorithme du tri par seau est de O(n^2), où n est le nombre d'éléments du tableau.
La complexité en espace est de O(n*k) dans le pire des cas.
Le tri par seau est régulièrement utilisé :
- Avec des valeurs à virgule flottante.
- Lorsque l'entrée est distribuée uniformément sur une plage.
Algorithme du tri par seau
bucketSort(array, size)
Entrées : Un tableau contenant les données à trier, et le nombre total des élément du tableau.
Sortie : Le tableau trié.
Début
bucketSort(A[], n)
1. Soit B[0....n-1] un nouveau tableau
2. pour i=0 à n-1
2.1. Faire de B[i] une liste vide
3. pour i=1 à n
3.1. faire insérer A[i] dans la liste B[n a[i]]
4. pour i=0 à n-1
4.1. trier la liste B[i] avec le tri insertion
5. Combiner les listes B[0], B[1],........, B[n-1] ensemble dans l'ordre
Fin
Complexité du tri par seau
À présent, voyons la complexité temporelle du tri par seau dans le meilleur des cas, dans le cas moyen et dans le pire des cas. Nous allons également voir la complexité spatiale du tri par seau.
1. Complexité en temps
| Cas |
Complexité |
| Meilleur des cas |
O(n + k) |
| Cas moyen |
O(n + k) |
| Pire des cas |
O(n^2) |
- Complexité dans le meilleur des cas : Elle se produit lorsqu'aucun tri n'est nécessaire, c'est-à-dire que le tableau est déjà trié. Dans le cas du tri par seau, le meilleur cas se produit lorsque les éléments sont uniformément répartis dans les compartiments. La complexité sera meilleure si les éléments sont déjà triés dans les compartiments.
Si nous utilisons le tri par insertion pour trier les éléments des compartiments, la complexité globale sera linéaire, c'est-à-dire O(n + k), où O(n) correspond à la création des compartiments et O(k) au tri des éléments des compartiments à l'aide d'algorithmes dont la complexité en temps est linéaire dans le meilleur des cas.
La complexité temporelle dans le meilleur des cas du tri par seau est de O(n + k).
- Complexité dans le cas moyen : Elle se produit lorsque les éléments du tableau sont dans un ordre désordonné qui n'est pas correctement ascendant et pas correctement descendant. Le tri par seau s'exécute en temps linéaire, même lorsque les éléments sont uniformément distribués. La complexité moyenne du tri par seau est de O(n + K).
- Complexité dans le pire des cas : Dans le tri par seau, le pire des cas se produit lorsque les éléments sont proches dans le tableau, ce qui fait qu'ils doivent être placés dans le même compartiment. Ainsi, certains compartiments ont plus d'éléments que d'autres.
La complexité augmente lorsque les éléments sont dans l'ordre inverse.
Dans le pire des cas, la complexité temporelle du tri par seau est de O(n^2).
2. Complexité en espace
| Complexité spatiale |
O(n*k) |
| Stable |
OUI |
La complexité en espace du tri par seau est de O(n*k).
Implémentation du tri par seau
Le code ci-dessous est une implémentation de l'algorithme du tri par seau en langage C.
#include <stdio.h>
// fonction pour obtenir le maximum d'un tableau
int getMax(int a[], int n) {
int max = a[0];
for (int i = 1; i < n; i++)
if (a[i] > max)
max = a[i];
return max;
}
// fonction du tri par seau
void bucket(int a[], int n) {
int max = getMax(a, n); // max est le maximum des éléments du tableau
int bucket[max], i;
for (int i = 0; i <= max; i++) {
bucket[i] = 0;
}
for (int i = 0; i < n; i++) {
bucket[a[i]]++;
}
for (int i = 0, j = 0; i <= max; i++) {
while (bucket[i] > 0) {
a[j++] = i;
bucket[i]--;
}
}
}
// fonction pour afficher les éléments du tableau
void printArr(int a[], int n) {
for (int i = 0; i < n; ++i)
printf("%d \t", a[i]);
printf("\n");
}
int main() {
int tab[] = {74, 35, 103, 57, 69, 41, 9, 17};
int n = sizeof(tab) / sizeof(tab[0]); // n est la taille du tableau
printf("Contenu du tableau avant le tri :\n");
printArr(tab, n);
bucket(tab, n);
printf("\nContenu du tableau après le tri :\n");
printArr(tab, n);
}
Résultat
L'exécution du code ci-dessus produit le résultat suivant :
Contenu du tableau avant le tri :
74 35 103 57 69 41 9 17
Contenu du tableau après le tri :
9 17 35 41 57 69 74 103