Ebben a cikkben a vödör rendezési algoritmusát tárgyaljuk. A vödör rendezésben lévő adatelemek gyűjtőhelyek formájában vannak elosztva. A szoftvermérnökök számára készített kódolási vagy technikai interjúk során széles körben felteszik a kérdést a rendezési algoritmusoknak. Ezért fontos a téma megvitatása.
A vödör rendezés egy rendezési algoritmus, amely az elemeket több csoportra osztja, amelyeket gyűjtőknek mondanak. A vödör rendezésben lévő elemeket először egységesen csoportokba osztják, amelyeket vödörnek neveznek, majd bármely más rendezési algoritmussal rendezik őket. Ezt követően az elemeket rendezett módon gyűjtik össze.
A vödör rendezés végrehajtásának alapvető eljárása a következő:
- Először particionálja a tartományt meghatározott számú gyűjtőcsoportra.
- Ezután dobjon minden elemet a megfelelő vödörbe.
- Ezt követően rendezze az egyes gyűjtőket egy-egy rendezési algoritmus alkalmazásával.
- És végül fűzze össze az összes kiválogatott vödröt.
A vödör rendezés előnyei:
- Vödör rendezés csökkenti a sz. az összehasonlításokról.
- Az elemek egyenletes eloszlása miatt aszimptotikusan gyors.
A vödör rendezés korlátai a következők:
- Lehet, hogy stabil rendezési algoritmus, de lehet, hogy nem.
- Nem hasznos, ha nagy tömbünk van, mert megnöveli a költségeket.
- Ez nem egy helyben történő rendezési algoritmus, mert szükség van némi extra helyre a vödrök rendezéséhez.
A vödör rendezés legjobb és átlagos összetettsége az O(n + k) , és a vödör rendezés legrosszabb összetettsége az Tovább2) , ahol n az elemek száma.
A vödör rendezést gyakran használják -
- Lebegőpontos értékekkel.
- Amikor a bemenet egyenletesen oszlik el egy tartományon belül.
A vödör rendezés végrehajtásának alapötlete a következő:
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
Most pedig lássuk a vödör rendezés algoritmusát.
Algoritmus
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-Gather megközelítés
A Bucket rendezési algoritmust szóródás-gyűjtő megközelítéssel érthetjük meg. Itt először vödrökbe szórják az adott elemeket. A szórás után az egyes gyűjtőkben lévő elemek egy stabil rendezési algoritmus segítségével rendeződnek. Végül a sorba rendezett elemek sorba kerülnek.
Vegyünk egy rendezetlen tömböt, hogy megértsük a vödör rendezés folyamatát. Egy példán keresztül könnyebb lesz megérteni a vödör rendezést.
Legyen a tömb elemei -
Most hozzon létre vödröket 0 és 25 közötti tartományban. A gyűjtőhelyek tartománya 0-5, 5-10, 10-15, 15-20, 20-25. Az elemeket a kanalak tartományának megfelelően helyezik be a kanalakba. Tegyük fel, hogy egy elem értéke 16, tehát a 15 és 20 közötti tartományba kerül be. Hasonlóképpen, a tömb minden eleme ennek megfelelően kerül beillesztésre.
Ez a fázis köztudottan a tömbelemek szórása .
Most, fajta minden vödör külön-külön. Az egyes kockák elemei a stabil rendezési algoritmusok bármelyikével rendezhetők.
Végül, összegyűjteni a rendezett elemeket az egyes vödrökből sorrendben
Most a tömb teljesen rendezve van.
Vödör rendezés összetettsége
Most pedig lássuk a vödör rendezés időbeli összetettségét legjobb, átlagos és legrosszabb esetben. Látni fogjuk a vödör rendezés térbeli összetettségét is.
1. Időbonyolultság
| Ügy | Idő | Bonyolultság |
|---|---|---|
| Legjobb eset | O(n + k) | |
| Átlagos eset | O(n + k) | |
| Legrosszabb esetben | Tovább2) |
Ha a beszúrásos rendezést használjuk a vödör elemek rendezésére, akkor a teljes összetettség lineáris lesz, azaz O(n + k), ahol O(n) a gyűjtődobozok készítésére szolgál, O(k) pedig a vödör elemek rendezésére. legjobb esetben lineáris időbonyolultságú algoritmusokat használva.
A vödör rendezés legjobb esetben az időbonyolultsága O(n + k) .
A bonyolultság még rosszabb lesz, ha az elemek fordított sorrendben vannak.
A vödör rendezés legrosszabb eseti összetettsége az Tovább2) .
2. A tér összetettsége
| A tér összetettsége | O(n*k) |
| Stabil | IGEN |
- A vödör rendezés térbeli összetettsége O(n*k).
Vödör rendezés megvalósítása
Most pedig lássuk a vödör rendezésű programokat különböző programozási nyelveken.
Program: Írjon programot a vödör rendezés megvalósítására C nyelven.
#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></=>