I denne artikel vil vi diskutere spandsorteringsalgoritmen. Dataelementerne i bucketsorteringen er fordelt i form af buckets. I kodnings- eller tekniske interviews for softwareingeniører er der mange spørgsmål om sorteringsalgoritmer. Så det er vigtigt at diskutere emnet.
Bucket sort er en sorteringsalgoritme, der adskiller elementerne i flere grupper, der siges at være buckets. Elementer i spandsortering opdeles først ensartet i grupper kaldet spande, og derefter sorteres de efter en hvilken som helst anden sorteringsalgoritme. Derefter samles elementer på en sorteret måde.
Den grundlæggende procedure for udførelse af spandsortering er givet som følger -
- Opdel først området i et fast antal spande.
- Smid derefter hvert element i dens passende spand.
- Sorter derefter hver spand individuelt ved at anvende en sorteringsalgoritme.
- Og til sidst, sammenkæde alle de sorterede spande.
Fordelene ved spandsortering er -
- Spandsortering reducerer antallet. af sammenligninger.
- Det er asymptotisk hurtigt på grund af den ensartede fordeling af elementer.
Begrænsningerne for spandsortering er -
- Det kan være eller ikke være en stabil sorteringsalgoritme.
- Det er ikke nyttigt, hvis vi har et stort array, fordi det øger omkostningerne.
- Det er ikke en in-place sorteringsalgoritme, fordi der kræves lidt ekstra plads til at sortere spandene.
Den bedste og gennemsnitlige kompleksitet af spandsortering er O(n + k) , og det værst tænkelige kompleksitet af spandsortering er På2) , hvor n er antallet af varer.
Spandsortering er almindeligt anvendt -
- Med floating-point værdier.
- Når input er fordelt ensartet over et interval.
Den grundlæggende idé til at udføre spandsortering er givet 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
Lad os nu se algoritmen for spandsortering.
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 tilgang
Vi kan forstå Bucket-sorteringsalgoritmen via scatter-gather-tilgang. Her bliver de givne elementer først spredt i spande. Efter spredning sorteres elementer i hver spand ved hjælp af en stabil sorteringsalgoritme. Til sidst vil de sorterede elementer blive samlet i rækkefølge.
Lad os tage et usorteret array for at forstå processen med spandsortering. Det vil være lettere at forstå spandsorteringen via et eksempel.
Lad elementerne i array være -
Opret nu spande med et interval fra 0 til 25. Spandeintervallet er 0-5, 5-10, 10-15, 15-20, 20-25. Elementer indsættes i spandene i henhold til spanderækken. Antag, at værdien af en vare er 16, så den vil blive indsat i bøtten med intervallet 15-20. På samme måde vil hvert element i arrayet indsættes i overensstemmelse hermed.
Denne fase er kendt for at være spredning af array-elementer .
Nu, sortere hver spand individuelt. Elementerne i hver spand kan sorteres ved at bruge en hvilken som helst af de stabile sorteringsalgoritmer.
Endelig, samle de sorterede elementer fra hver spand i rækkefølge
Nu er arrayet helt sorteret.
Skovlsorteringskompleksitet
Lad os nu se tidskompleksiteten af spandsortering i bedste tilfælde, gennemsnitligt tilfælde og i værste tilfælde. Vi vil også se pladskompleksiteten af spandsorten.
1. Tidskompleksitet
| Sag | Tid | Kompleksitet |
|---|---|---|
| Bedste sag | O(n + k) | |
| Gennemsnitlig tilfælde | O(n + k) | |
| Worst Case | På2) |
Hvis vi bruger indsættelsessorteringen til at sortere spandeelementerne, vil den overordnede kompleksitet være lineær, dvs. O(n + k), hvor O(n) er til fremstilling af spandene, og O(k) er for sortering af spandelementerne ved hjælp af algoritmer med lineær tidskompleksitet i bedste fald.
Den bedste tidskompleksitet af spandsortering er O(n + k) .
Kompleksiteten bliver værre, når elementerne er i omvendt rækkefølge.
Den værste tidskompleksitet af spandsortering er På2) .
2. Rumkompleksitet
| Rumkompleksitet | O(n*k) |
| Stabil | JA |
- Rumkompleksiteten af spandsortering er O(n*k).
Implementering af spandsortering
Lad os nu se programmerne for bucket-sortering på forskellige programmeringssprog.
Program: Skriv et program til at implementere spandsortering i C-sprog.
#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></=>