logo

TechCodeview

Algoritmus triedenia vedra

V tomto článku budeme diskutovať o algoritme triedenia vedra. Dátové položky v triedení segmentov sú distribuované vo forme segmentov. Pri kódovaní alebo technických pohovoroch pre softvérových inžinierov sú často kladené otázky na triediace algoritmy. Preto je dôležité diskutovať o téme.

Zoradenie segmentov je triediaci algoritmus, ktorý rozdeľuje prvky do viacerých skupín, ktoré sa označujú ako segmenty. Prvky v segmentovom triedení sú najprv jednotne rozdelené do skupín nazývaných segmenty a potom sú triedené podľa akéhokoľvek iného triediaceho algoritmu. Potom sa prvky zhromaždia triedeným spôsobom.

Základný postup vykonávania triedenia vedierka je uvedený nasledovne -

  • Najprv rozdeľte rozsah do pevného počtu vedier.
  • Potom hoďte každý prvok do príslušného vedra.
  • Potom zoraďte každý segment jednotlivo pomocou triediaceho algoritmu.
  • A nakoniec zreťazte všetky vytriedené vedrá.

Výhody triedenia vedier sú -

  • Triedenie vedier znižuje č. porovnaní.
  • Je asymptoticky rýchly kvôli rovnomernému rozloženiu prvkov.

Obmedzenia triedenia vedra sú -

  • Môže alebo nemusí ísť o stabilný triediaci algoritmus.
  • Nie je to užitočné, ak máme veľké pole, pretože to zvyšuje náklady.
  • Nie je to miestny triediaci algoritmus, pretože na triedenie vedier je potrebný určitý priestor navyše.

Najlepšia a priemerná zložitosť triedenia vedra je O(n + k) a najhorší prípad zložitosti triedenia segmentov je O(n2) , kde n je počet položiek.

Bežne sa používa triedenie vedier -

  • S hodnotami s pohyblivou rádovou čiarkou.
  • Keď je vstup distribuovaný rovnomerne v rámci rozsahu.

Základná myšlienka na vykonanie triedenia vedra je daná nasledovne -

 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

Teraz sa pozrime na algoritmus triedenia segmentov.

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

Rozptylový prístup

Algoritmus triedenia Bucket môžeme pochopiť pomocou metódy scatter-gather. Tu sa dané prvky najskôr rozsypú do vedier. Po rozptýlení sa prvky v každom vedre triedia pomocou stabilného triediaceho algoritmu. Nakoniec sa zoradené prvky zhromaždia v poradí.

Zoberme si netriedené pole, aby sme pochopili proces triedenia vedra. Pomocou príkladu bude jednoduchšie pochopiť triedenie vedra.

Nech sú prvky poľa -

vedro triediť

Teraz vytvorte segmenty s rozsahom od 0 do 25. Rozsah segmentov je 0-5, 5-10, 10-15, 15-20, 20-25. Prvky sa vkladajú do vedier podľa rozsahu vedier. Predpokladajme, že hodnota položky je 16, takže bude vložená do vedra s rozsahom 15-20. Podobne sa vloží každá položka poľa.

Táto fáza je známa ako rozptyl prvkov poľa .

vedro triediť

teraz triediť každé vedro jednotlivo. Prvky každého segmentu je možné triediť pomocou ktoréhokoľvek zo stabilných algoritmov triedenia.

vedro triediť

Nakoniec, zhromaždiť zoradené prvky z každého vedra v poradí

vedro triediť

Teraz je pole úplne zoradené.

Zložitosť triedenia vedier

Teraz sa pozrime na časovú zložitosť triedenia segmentov v najlepšom prípade, priemernom prípade a v najhoršom prípade. Uvidíme aj priestorovú náročnosť triedenia vedier.

1. Časová zložitosť

Prípad Čas Zložitosť
Najlepší prípad O(n + k)
Priemerný prípad O(n + k)
V najhoršom prípade O(n2)
    Najlepšia zložitosť prípadu -Vyskytuje sa, keď nie je potrebné žiadne triedenie, t. j. pole je už zoradené. Pri triedení Bucket najlepší prípad nastane, keď sú prvky rovnomerne rozložené vo vedrách. Zložitosť bude lepšia, ak sú prvky už zoradené vo vedrách.
    Ak použijeme triedenie vloženia na triedenie prvkov vedra, celková zložitosť bude lineárna, t. j. O(n + k), kde O(n) je na vytváranie vedier a O(k) je na triedenie prvkov vedra. v najlepšom prípade pomocou algoritmov s lineárnou časovou zložitosťou.
    Najlepšia časová zložitosť triedenia vedra je O(n + k) .Priemerná zložitosť prípadu -Vyskytuje sa vtedy, keď sú prvky poľa v premiešanom poradí, ktoré nie je správne vzostupné a nesprávne zostupné. Triedenie vedie v lineárnom čase, aj keď sú prvky rovnomerne rozložené. Priemerná časová zložitosť triedenia segmentov je O(n + K) .Zložitosť najhoršieho prípadu -Pri triedení segmentov najhorší prípad nastane, keď sú prvky v poli v blízkom rozsahu, preto musia byť umiestnené v rovnakom segmente. Takže niektoré vedrá majú viac prvkov ako iné.
    Zložitosť sa zhorší, keď sú prvky v opačnom poradí.
    Najhorší prípad časovej zložitosti triedenia vedra je O(n2) .

2. Zložitosť priestoru

Priestorová zložitosť O(n*k)
Stabilný ÁNO
  • Priestorová zložitosť triedenia segmentov je O(n*k).

Implementácia triedenia vedier

Teraz sa pozrime na programy triedenia bucketov v rôznych programovacích jazykoch.

Program: Napíšte program na implementáciu triedenia segmentov v jazyku 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&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></=>