În acest articol, vom discuta despre algoritmul de sortare a găleților. Elementele de date din sortarea găleților sunt distribuite sub formă de găleți. În interviurile de codificare sau tehnice pentru inginerii de software, algoritmii de sortare sunt solicitați pe scară largă. Deci, este important să discutăm subiectul.
Bucket sort este un algoritm de sortare care separă elementele în mai multe grupuri despre care se spune că sunt găleți. Elementele din sortarea găleților sunt mai întâi împărțite uniform în grupuri numite găleți și apoi sunt sortate de orice alt algoritm de sortare. După aceea, elementele sunt adunate într-o manieră sortată.
Procedura de bază de efectuare a sortării cupei este dată după cum urmează -
- Mai întâi, împărțiți domeniul într-un număr fix de găleți.
- Apoi, aruncați fiecare element în găleata corespunzătoare.
- După aceea, sortați fiecare găleată individual, aplicând un algoritm de sortare.
- Și, în cele din urmă, concatenează toate gălețile sortate.
Avantajele sortării cu găleată sunt:
- Sortarea cu găleată reduce numărul. de comparatii.
- Este asimptotic rapid din cauza distribuției uniforme a elementelor.
Limitările sortării cu găleți sunt -
- Poate fi sau nu un algoritm de sortare stabil.
- Nu este util dacă avem o matrice mare, deoarece crește costul.
- Nu este un algoritm de sortare in loc, deoarece este necesar un spațiu suplimentar pentru sortarea găleților.
Cea mai bună și medie complexitate a tipului de găleți este O(n + k) , iar cel mai rău caz de complexitate a sortării cu găleți este Pe2) , Unde n este numărul de articole.
Sortarea cu găleată este folosită în mod obișnuit -
- Cu valori în virgulă mobilă.
- Când intrarea este distribuită uniform într-un interval.
Ideea de bază pentru a efectua sortarea găleții este dată după cum urmează -
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
Acum, să vedem algoritmul de sortare a găleților.
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
Abordarea dispersie-adunare
Putem înțelege algoritmul de sortare Bucket prin abordarea scatter-gather. Aici, elementele date sunt mai întâi împrăștiate în găleți. După împrăștiere, elementele din fiecare găleată sunt sortate folosind un algoritm de sortare stabil. În cele din urmă, elementele sortate vor fi adunate în ordine.
Să luăm o matrice nesortată pentru a înțelege procesul de sortare a găleților. Va fi mai ușor de înțeles sortarea găleții printr-un exemplu.
Fie elementele matricei sunt -
Acum, creați găleți cu un interval de la 0 la 25. Intervalul de găleți este 0-5, 5-10, 10-15, 15-20, 20-25. Elementele sunt introduse în găleți în funcție de gama de găleți. Să presupunem că valoarea unui articol este 16, deci va fi introdus în găleată cu intervalul 15-20. În mod similar, fiecare element al matricei va fi inserat corespunzător.
Această fază este cunoscută a fi împrăștierea elementelor matricei .
Acum, fel fiecare găleată individual. Elementele fiecărei găleți pot fi sortate folosind oricare dintre algoritmii de sortare stabili.
În sfârșit, aduna elementele sortate din fiecare găleată în ordine
Acum, matricea este complet sortată.
Complexitatea sortării găleții
Acum, să vedem complexitatea de timp a sortării găleții în cel mai bun caz, mediu și în cel mai rău caz. Vom vedea, de asemenea, complexitatea spațială a tipului de găleți.
1. Complexitatea timpului
| Caz | Timp | Complexitate |
|---|---|---|
| Cel mai bun caz | O(n + k) | |
| Caz mediu | O(n + k) | |
| Cel mai rău caz | Pe2) |
Dacă folosim sortarea prin inserție pentru a sorta elementele găleții, complexitatea generală va fi liniară, adică O(n + k), unde O(n) este pentru realizarea găleților și O(k) este pentru sortarea elementelor găleților. folosind algoritmi cu complexitate liniară de timp în cel mai bun caz.
Cel mai bun caz, complexitatea timpului de sortare a găleților este O(n + k) .
Complexitatea se va agrava atunci când elementele sunt în ordine inversă.
Cel mai rău caz complexitatea timpului de sortare a găleților este Pe2) .
2. Complexitatea spațială
| Complexitatea spațială | O(n*k) |
| Grajd | DA |
- Complexitatea spațială a sortării găleții este O(n*k).
Implementarea sortării cu găleată
Acum, să vedem programele de tip bucket sort în diferite limbaje de programare.
Program: Scrieți un program pentru a implementa sortarea găleților în limbajul 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></=>