I denne artikkelen vil vi diskutere bøttesorteringsalgoritmen. Dataelementene i bøttesortering er fordelt i form av bøtte. I koding eller tekniske intervjuer for programvareingeniører er det mye spørsmål om sorteringsalgoritmer. Så det er viktig å diskutere temaet.
Bøttesortering er en sorteringsalgoritme som skiller elementene i flere grupper som sies å være bøtter. Elementer i bøttesortering blir først jevnt delt inn i grupper kalt bøtte, og deretter sorteres de etter en hvilken som helst annen sorteringsalgoritme. Etter det samles elementer på en sortert måte.
Den grunnleggende prosedyren for å utføre bøttesortering er gitt som følger -
- Del først opp området i et fast antall bøtter.
- Deretter kaster du hvert element i den passende bøtten.
- Deretter sorterer du hver bøtte individuelt ved å bruke en sorteringsalgoritme.
- Og til slutt, slå sammen alle de sorterte bøttene.
Fordelene med bøttesortering er -
- Bøttesortering reduserer antall. av sammenligninger.
- Det er asymptotisk raskt på grunn av den jevne fordelingen av elementer.
Begrensningene for bøttesortering er -
- Det kan være en stabil sorteringsalgoritme eller ikke.
- Det er ikke nyttig hvis vi har et stort utvalg fordi det øker kostnadene.
- Det er ikke en in-place sorteringsalgoritme, fordi det kreves litt ekstra plass for å sortere bøttene.
Den beste og gjennomsnittlige kompleksiteten til bøttesortering er O(n + k) , og det verste tilfellet av bøttesortering er På2) , hvor n er antall varer.
Bøttesortering er ofte brukt -
- Med flyttallsverdier.
- Når input er jevnt fordelt over et område.
Den grunnleggende ideen for å utføre bøttesortering er gitt som følger -
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
La oss nå se algoritmen for bøttesortering.
Algoritme
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
Scatter-samler-tilnærming
Vi kan forstå Bucket-sorteringsalgoritmen via scatter-gather-tilnærming. Her blir de gitte elementene først spredt i bøtter. Etter spredning sorteres elementene i hver bøtte ved hjelp av en stabil sorteringsalgoritme. Til slutt vil de sorterte elementene bli samlet i rekkefølge.
La oss ta en usortert matrise for å forstå prosessen med bøttesortering. Det vil være lettere å forstå bøttesorteringen via et eksempel.
La elementene i array være -
Lag nå bøtter med et område fra 0 til 25. Bøtteområdet er 0-5, 5-10, 10-15, 15-20, 20-25. Elementer settes inn i bøttene i henhold til bøtteområdet. Anta at verdien av en vare er 16, så den legges inn i bøtta med området 15-20. På samme måte vil hvert element i matrisen settes inn tilsvarende.
Denne fasen er kjent for å være spredning av array-elementer .
Nå, sortere hver bøtte individuelt. Elementene i hver bøtte kan sorteres ved å bruke hvilken som helst av de stabile sorteringsalgoritmene.
Endelig, samle de sorterte elementene fra hver bøtte i rekkefølge
Nå er matrisen fullstendig sortert.
Bøttesorteringskompleksitet
La oss nå se tidskompleksiteten til bøttesortering i beste fall, gjennomsnittlig tilfelle og i verste fall. Vi vil også se plasskompleksiteten til bøttesorten.
1. Tidskompleksitet
| Sak | Tid | Kompleksitet |
|---|---|---|
| Beste sak | O(n + k) | |
| Gjennomsnittlig sak | O(n + k) | |
| Worst Case | På2) |
Hvis vi bruker innsettingssorteringen for å sortere bøtteelementene, vil den generelle kompleksiteten være lineær, dvs. O(n + k), der O(n) er for å lage bøttene, og O(k) er for å sortere bøtteelementene ved å bruke algoritmer med lineær tidskompleksitet i beste fall.
Den beste tidskompleksiteten til bøttesortering er O(n + k) .
Kompleksiteten vil bli verre når elementene er i omvendt rekkefølge.
Den verste tid kompleksiteten av bøtte sortering er På2) .
2. Romkompleksitet
| Plass kompleksitet | O(n*k) |
| Stabil | JA |
- Plasskompleksiteten til bøttesortering er O(n*k).
Gjennomføring av bøttesortering
La oss nå se programmene for bøttesortering på forskjellige programmeringsspråk.
Program: Skriv et program for å implementere bøttesortering i C-språk.
#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></=>