In dit artikel bespreken we het bucket-sort-algoritme. De gegevensitems in de bucket-sortering worden verdeeld in de vorm van buckets. In codeer- of technische interviews voor software-ingenieurs wordt veel gevraagd naar sorteeralgoritmen. Het is dus belangrijk om het onderwerp te bespreken.
Bucket sort is een sorteeralgoritme dat de elementen in meerdere groepen scheidt, zogenaamde buckets. Elementen bij het sorteren van emmers worden eerst uniform verdeeld in groepen die buckets worden genoemd, en vervolgens worden ze gesorteerd door een ander sorteeralgoritme. Daarna worden de elementen gesorteerd verzameld.
De basisprocedure voor het uitvoeren van de emmersortering is als volgt:
- Verdeel eerst het bereik in een vast aantal buckets.
- Gooi vervolgens elk element in de juiste emmer.
- Sorteer daarna elke emmer afzonderlijk door een sorteeralgoritme toe te passen.
- En voeg ten slotte alle gesorteerde emmers samen.
De voordelen van emmersoort zijn:
- Emmersoort vermindert het aantal. van vergelijkingen.
- Het is asymptotisch snel vanwege de uniforme verdeling van elementen.
De beperkingen van het sorteren van emmers zijn -
- Het kan wel of niet een stabiel sorteeralgoritme zijn.
- Het is niet nuttig als we een grote array hebben, omdat dit de kosten verhoogt.
- Het is geen in-place sorteeralgoritme, omdat er wat extra ruimte nodig is om de emmers te sorteren.
De beste en gemiddelde complexiteit van emmersoort is O(n + k) , en de worst-case complexiteit van bucket-sortering is Op2) , waar N is het aantal artikelen.
Emmersoort wordt vaak gebruikt -
- Met drijvende-kommawaarden.
- Wanneer de invoer uniform over een bereik wordt verdeeld.
Het basisidee om de bucket-sortering uit te voeren is als volgt:
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
Laten we nu eens kijken naar het algoritme voor het sorteren van emmers.
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
Verspreid-verzamel-aanpak
We kunnen het Bucket-sorteeralgoritme begrijpen via een scatter-gather-aanpak. Hier worden de gegeven elementen eerst in emmers verspreid. Na verstrooiing worden de elementen in elke emmer gesorteerd met behulp van een stabiel sorteeralgoritme. Eindelijk worden de gesorteerde elementen op volgorde verzameld.
Laten we een ongesorteerde array nemen om het proces van bucketsortering te begrijpen. Het zal gemakkelijker zijn om de emmersoort te begrijpen aan de hand van een voorbeeld.
Laat de elementen van array zijn -
Maak nu buckets met een bereik van 0 tot 25. Het bereik van de buckets is 0-5, 5-10, 10-15, 15-20, 20-25. Afhankelijk van het bereik van de bakken worden elementen in de bakken geplaatst. Stel dat de waarde van een item 16 is, dan wordt het in de bucket geplaatst met een bereik van 15-20. Op dezelfde manier wordt elk item van de array dienovereenkomstig ingevoegd.
Deze fase staat bekend als de verstrooiing van array-elementen .
Nu, soort elke emmer afzonderlijk. De elementen van elke bucket kunnen worden gesorteerd met behulp van een van de stabiele sorteeralgoritmen.
Eindelijk, bijeenkomen de gesorteerde elementen uit elke emmer op volgorde
Nu is de array volledig gesorteerd.
Complexiteit van het sorteren van buckets
Laten we nu eens kijken naar de tijdscomplexiteit van het sorteren van emmers in het beste geval, het gemiddelde geval en in het slechtste geval. We zullen ook de ruimtecomplexiteit van de emmersoort zien.
1. Tijdcomplexiteit
| Geval | Tijd | Complexiteit |
|---|---|---|
| Beste geval | O(n + k) | |
| Gemiddeld geval | O(n + k) | |
| Het slechtste geval | Op2) |
Als we de invoegsortering gebruiken om de bucket-elementen te sorteren, zal de algehele complexiteit lineair zijn, dat wil zeggen O(n + k), waarbij O(n) is voor het maken van de buckets, en O(k) voor het sorteren van de bucket-elementen. in het beste geval gebruik te maken van algoritmen met lineaire tijdscomplexiteit.
De beste tijdscomplexiteit van het sorteren van emmers is O(n + k) .
De complexiteit wordt erger als de elementen zich in de omgekeerde volgorde bevinden.
De worst-case tijdscomplexiteit van emmersoort is Op2) .
2. Ruimtecomplexiteit
| Ruimtecomplexiteit | O(n*k) |
| Stal | JA |
- De ruimtecomplexiteit van bucket-sortering is O(n*k).
Implementatie van emmersoort
Laten we nu de programma's van Bucket Sort in verschillende programmeertalen bekijken.
Programma: Schrijf een programma om bucketsortering in C-taal te implementeren.
#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></=>