I den här artikeln kommer vi att diskutera algoritmen för hinksortering. Dataposterna i hinksorteringen fördelas i form av hinkar. I kodnings- eller tekniska intervjuer för mjukvaruingenjörer är sorteringsalgoritmer många frågade. Så det är viktigt att diskutera ämnet.

Hinksortering är en sorteringsalgoritm som separerar elementen i flera grupper som sägs vara hinkar. Element i hinksortering delas först enhetligt in i grupper som kallas hinkar, och sedan sorteras de med någon annan sorteringsalgoritm. Därefter samlas element på ett sorterat sätt.

Den grundläggande proceduren för att utföra skopsortering ges enligt följande -

• Dela först upp intervallet i ett fast antal hinkar.
• Kasta sedan varje element i sin lämpliga hink.
• Efter det, sortera varje hink individuellt genom att använda en sorteringsalgoritm.
• Och till sist, sammanfoga alla sorterade hinkar.

Fördelarna med hinksortering är -

• Skoksortering minskar antalet. av jämförelser.
• Det är asymptotiskt snabbt på grund av den enhetliga fördelningen av element.

Begränsningarna för hinksortering är -

• Det kan eller kanske inte är en stabil sorteringsalgoritm.
• Det är inte användbart om vi har en stor array eftersom det ökar kostnaden.
• Det är inte en på plats sorteringsalgoritm, eftersom det krävs lite extra utrymme för att sortera hinkarna.

Den bästa och genomsnittliga komplexiteten av hinksortering är O(n + k) , och det värsta tänkbara komplexiteten med hinksortering är På²) , var n är antalet föremål.

Skopsortering används ofta -

• Med flyttalsvärden.
• När input är jämnt fördelat över ett intervall.

Grundidén för att utföra skopsortering ges enligt följande -

 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 

Låt oss nu se algoritmen för hinksortering.

Algoritm

 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-samla tillvägagångssätt

Vi kan förstå Bucket-sorteringsalgoritmen via scatter-gather-metoden. Här sprids de givna elementen först ut i hinkar. Efter spridning sorteras elementen i varje hink med hjälp av en stabil sorteringsalgoritm. Äntligen kommer de sorterade elementen att samlas i ordning.

Låt oss ta en osorterad array för att förstå processen med hinksortering. Det blir lättare att förstå skopsorten via ett exempel.

Låt elementen i arrayen vara -

Skapa nu hinkar med ett intervall från 0 till 25. Buckets intervall är 0-5, 5-10, 10-15, 15-20, 20-25. Element sätts in i hinkarna enligt skopsortimentet. Anta att värdet på en vara är 16, så den kommer att läggas i hinken med intervallet 15-20. På samma sätt kommer varje objekt i arrayen att infogas därefter.

Denna fas är känd för att vara spridning av arrayelement .

Nu, sortera varje hink individuellt. Elementen i varje hink kan sorteras genom att använda någon av de stabila sorteringsalgoritmerna.

Äntligen, samla de sorterade elementen från varje hink i ordning

Nu är arrayen helt sorterad.

Skopsorteringskomplexitet

Låt oss nu se tidskomplexiteten för skopsortering i bästa fall, genomsnittligt fall och i värsta fall. Vi kommer också att se utrymmeskomplexiteten hos skopans sortering.

1. Tidskomplexitet

Best Case Complexity -Det inträffar när det inte krävs någon sortering, dvs arrayen är redan sorterad. I hinksortering inträffar det bästa fallet när elementen är jämnt fördelade i hinkarna. Komplexiteten blir bättre om elementen redan är sorterade i hinkarna.
Om vi ​​använder infogningssorteringen för att sortera hinkelementen kommer den övergripande komplexiteten att vara linjär, dvs O(n + k), där O(n) är för att tillverka skoporna och O(k) är för att sortera hinkelementen använda algoritmer med linjär tidskomplexitet i bästa fall.
Den bästa möjliga tidskomplexiteten för hinksortering är O(n + k) .Genomsnittlig ärendekomplexitet -Det inträffar när arrayelementen är i blandad ordning som inte är korrekt stigande och inte korrekt fallande. Hinksortering körs i linjär tid, även när elementen är jämnt fördelade. Den genomsnittliga falltidskomplexiteten för hinksortering är O(n + K) .Worst Case Complexity -I bucket-sortering inträffar värsta fall när elementen är på nära håll i arrayen, på grund av det måste de placeras i samma hink. Så vissa hinkar har fler element än andra.
Komplexiteten blir värre när elementen är i omvänd ordning.
Den värsta tänkbara tidskomplexiteten för hinksortering är På²) .

2. Rymdkomplexitet

• Utrymmeskomplexiteten för skopsortering är O(n*k).

Implementering av hinksortering

Låt oss nu se programmen för hinksortering på olika programmeringsspråk.

Program: Skriv ett program för att implementera hinksortering 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&apos;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></=>