Dans cet article, nous aborderons l’algorithme de tri par compartiment. Les éléments de données du tri par compartiment sont distribués sous forme de compartiments. Lors des entretiens de codage ou techniques pour les ingénieurs logiciels, les algorithmes de tri sont largement sollicités. Il est donc important d’aborder le sujet.
Le tri par compartiment est un algorithme de tri qui sépare les éléments en plusieurs groupes appelés compartiments. Les éléments du tri par compartiment sont d'abord divisés uniformément en groupes appelés compartiments, puis triés par tout autre algorithme de tri. Après cela, les éléments sont rassemblés de manière triée.
La procédure de base pour effectuer le tri par compartiment est la suivante :
- Tout d’abord, divisez la plage en un nombre fixe de compartiments.
- Ensuite, jetez chaque élément dans son seau approprié.
- Après cela, triez chaque compartiment individuellement en appliquant un algorithme de tri.
- Et enfin, concaténez tous les buckets triés.
Les avantages du tri par seau sont :
- Le tri par seau réduit le nombre de personnes. de comparaisons.
- Il est asymptotiquement rapide en raison de la distribution uniforme des éléments.
Les limites du tri par compartiment sont :
- Il peut s'agir ou non d'un algorithme de tri stable.
- Ce n’est pas utile si nous avons un grand réseau car cela augmente le coût.
- Il ne s'agit pas d'un algorithme de tri sur place, car un espace supplémentaire est nécessaire pour trier les compartiments.
La complexité optimale et moyenne du tri par compartiment est O(n+k) , et la complexité du tri par compartiment dans le pire des cas est Sur2) , où n est le nombre d'éléments.
Le tri par seau est couramment utilisé -
- Avec des valeurs à virgule flottante.
- Lorsque l’entrée est répartie uniformément sur une plage.
L'idée de base pour effectuer le tri par compartiment est donnée comme suit :
bucketSort(a[], n) 1. Create 'n' empty buckets 2. Do for each array element a[i] 2.1. Put array elements into buckets, i.e. insert a[i] into bucket[n*a[i]] 3. Sort the elements of individual buckets by using the insertion sort. 4. At last, gather or concatenate the sorted buckets. End bucketSort
Voyons maintenant l'algorithme de tri par bucket.
Algorithme
Bucket Sort(A[]) 1. Let B[0....n-1] be a new array 2. n=length[A] 3. for i=0 to n-1 4. make B[i] an empty list 5. for i=1 to n 6. do insert A[i] into list B[n a[i]] 7. for i=0 to n-1 8. do sort list B[i] with insertion-sort 9. Concatenate lists B[0], B[1],........, B[n-1] together in order End
Approche de dispersion
Nous pouvons comprendre l'algorithme de tri Bucket via une approche scatter-gather. Ici, les éléments donnés sont d'abord dispersés dans des compartiments. Après diffusion, les éléments de chaque compartiment sont triés à l'aide d'un algorithme de tri stable. Enfin, les éléments triés seront rassemblés dans l'ordre.
Prenons un tableau non trié pour comprendre le processus de tri par bucket. Il sera plus facile de comprendre le tri par bucket via un exemple.
Soit les éléments du tableau -
Maintenant, créez des compartiments avec une plage de 0 à 25. Les plages de compartiments sont 0-5, 5-10, 10-15, 15-20, 20-25. Les éléments sont insérés dans les buckets en fonction de la plage du bucket. Supposons que la valeur d'un élément soit de 16, il sera donc inséré dans le compartiment avec une plage comprise entre 15 et 20. De même, chaque élément du tableau sera inséré en conséquence.
Cette phase est connue pour être la diffusion des éléments du tableau .
Maintenant, trier chaque seau individuellement. Les éléments de chaque compartiment peuvent être triés à l'aide de l'un des algorithmes de tri stables.
Enfin, rassembler les éléments triés de chaque compartiment dans l'ordre
Maintenant, le tableau est complètement trié.
Complexité du tri par compartiment
Voyons maintenant la complexité temporelle du tri par compartiment dans le meilleur des cas, le cas moyen et le pire des cas. Nous verrons également la complexité spatiale du tri par bucket.
1. Complexité temporelle
| Cas | Temps | Complexité |
|---|---|---|
| Meilleur cas | O(n+k) | |
| Cas moyen | O(n+k) | |
| Pire cas | Sur2) |
Si nous utilisons le tri par insertion pour trier les éléments du bucket, la complexité globale sera linéaire, c'est-à-dire O(n + k), où O(n) sert à créer les buckets et O(k) sert à trier les éléments du bucket. en utilisant des algorithmes avec une complexité temporelle linéaire dans le meilleur des cas.
Dans le meilleur des cas, la complexité temporelle du tri par compartiment est O(n+k) .
La complexité s’aggravera lorsque les éléments seront dans l’ordre inverse.
La complexité temporelle dans le pire des cas du tri par compartiment est Sur2) .
2. Complexité spatiale
| Complexité spatiale | O(n*k) |
| Écurie | OUI |
- La complexité spatiale du tri par compartiment est O(n*k).
Implémentation du tri par buckets
Voyons maintenant les programmes de tri par buckets dans différents langages de programmation.
Programme: Écrivez un programme pour implémenter le tri par buckets en langage C.
#include int getMax(int a[], int n) // function to get maximum element from the given array { int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } void bucket(int a[], int n) // function to implement bucket sort { int max = getMax(a, n); //max is the maximum element of array int bucket[max], i; for (int i = 0; i <= max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; void printarr(int a[], int n) function to print array elements ++i) printf('%d ', a[i]); main() a[]="{54," 12, 84, 57, 69, 41, 9, 5}; n="sizeof(a)" sizeof(a[0]); is the size of printf('before sorting are -
'); printarr(a, n); bucket(a, printf('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-5.webp" alt="bucket sort"> <p> <strong>Program:</strong> Write a program to implement bucket sort in C++.</p> <pre> #include using namespace std; int getMax(int a[], int n) // function to get maximum element from the given array { int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } void bucket(int a[], int n) // function to implement bucket sort { int max = getMax(a, n); //max is the maximum element of array int bucket[max], i; for (int i = 0; i <= max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; void printarr(int a[], int n) function to print array elements ++i) cout< <a[i]<<' '; main() a[]="{34," 42, 74, 57, 99, 84, 9, 5}; n="sizeof(a)" sizeof(a[0]); is the size of cout<<'before sorting are -
'; printarr(a, n); bucket(a, cout<<'
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-6.webp" alt="bucket sort"> <p> <strong>Program:</strong> Write a program to implement bucket sort in C#.</p> <pre> using System; class Bucket { static int getMax(int[] a) // function to get maximum element from the given array { int n = a.Length; int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } static void bucket(int[] a) // function to implement bucket sort { int n = a.Length; int max = getMax(a); //max is the maximum element of array int[] bucket = new int[max+1]; for (int i = 0; i <= 10 max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; static void printarr(int[] a) * function to print the array int i; n="a.Length;" (i="0;" console.write(a[i] + ' '); main() int[] a="{" 95, 50, 45, 15, 20, }; console.write('before sorting elements are -
'); printarr(a); bucket(a); console.write('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-7.webp" alt="bucket sort"> <p> <strong>Program:</strong> Write a program to implement bucket sort in Java.</p> <pre> public class Bucket { int getMax(int a[]) // function to get maximum element from the given array { int n = a.length; int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } void bucket(int a[]) // function to implement bucket sort { int n = a.length; int max = getMax(a); //max is the maximum element of array int bucket[] = new int[max+1]; for (int i = 0; i <= 9 max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; void printarr(int a[]) * function to print the array int i; n="a.length;" (i="0;" system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 90, 40, 5, 15, 30, }; bucket b1="new" bucket(); system.out.print('before sorting elements are -
'); b1.printarr(a); b1.bucket(a); system.out.print('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-8.webp" alt="bucket sort"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. Along with the algorithm, we have also discussed the bucket sort complexity, working, and implementation in different programming languages.</p> <hr></=></pre></=></pre></=></pre></=>