logo

TechCodeview

Kausu kārtošanas algoritms

Šajā rakstā mēs apspriedīsim kausa kārtošanas algoritmu. Datu vienumi segmentu kārtošanā tiek izplatīti segmentu veidā. Programmatūras inženieru kodēšanas vai tehniskajās intervijās plaši tiek uzdoti šķirošanas algoritmi. Tāpēc ir svarīgi apspriest tēmu.

Segu kārtošana ir kārtošanas algoritms, kas sadala elementus vairākās grupās, kas tiek uzskatītas par segmentiem. Kategorijas elementi vispirms tiek vienmērīgi sadalīti grupās, ko sauc par segmentiem, un pēc tam tie tiek sakārtoti pēc jebkura cita šķirošanas algoritma. Pēc tam elementi tiek apkopoti sakārtotā veidā.

Kausu kārtošanas pamatprocedūra ir dota šādi:

  • Pirmkārt, sadaliet diapazonu noteiktā skaitā segmentu.
  • Pēc tam iemetiet katru elementu atbilstošajā spainī.
  • Pēc tam kārtojiet katru spaini atsevišķi, izmantojot kārtošanas algoritmu.
  • Un visbeidzot, savienojiet visus sašķirotos spaiņus.

Kausu šķirošanas priekšrocības ir:

  • Kausa šķirošana samazina Nr. no salīdzinājumiem.
  • Tas ir asimptotiski ātrs elementu vienmērīgā sadalījuma dēļ.

Kausu šķirošanas ierobežojumi ir:

  • Tas var būt vai nebūt stabils šķirošanas algoritms.
  • Tas nav lietderīgi, ja mums ir liels masīvs, jo tas palielina izmaksas.
  • Tas nav kārtošanas algoritms uz vietas, jo spaiņu šķirošanai ir nepieciešama papildu vieta.

Labākā un vidējā sarežģītības pakāpe kausu šķirošanai ir O(n+k) , un kausa kārtošanas sarežģītākā gadījuma sarežģītība ir O(n2) , kur n ir vienumu skaits.

Parasti tiek izmantota kausu šķirošana -

  • Ar peldošā komata vērtībām.
  • Kad ievade ir vienmērīgi sadalīta diapazonā.

Pamatideja veikt kausu kārtošanu ir sniegta šādi -

 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

Tagad apskatīsim kausa kārtošanas algoritmu.

Algoritms

 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

Izkliedes un savākšanas pieeja

Mēs varam saprast segmenta kārtošanas algoritmu, izmantojot izkliedes-vācot pieeju. Šeit dotie elementi vispirms tiek izkaisīti spaiņos. Pēc izkliedēšanas elementi katrā segmentā tiek sakārtoti, izmantojot stabilu šķirošanas algoritmu. Beidzot sakārtotie elementi tiks apkopoti kārtībā.

Paņemsim nešķirotu masīvu, lai saprastu kausa kārtošanas procesu. Izmantojot piemēru, būs vieglāk saprast kausa kārtošanu.

Lai masīva elementi ir -

kausa šķirošana

Tagad izveidojiet segmentus ar diapazonu no 0 līdz 25. Segmentu diapazons ir 0-5, 5-10, 10-15, 15-20, 20-25. Elementi tiek ievietoti kausos atbilstoši kausu diapazonam. Pieņemsim, ka vienuma vērtība ir 16, tātad tas tiks ievietots segmentā ar diapazonu no 15 līdz 20. Tāpat katrs masīva vienums tiks attiecīgi ievietots.

Ir zināms, ka šī fāze ir masīva elementu izkliedēšana .

kausa šķirošana

Tagad kārtot katrs spainis atsevišķi. Katra kausa elementus var kārtot, izmantojot jebkuru no stabilajiem šķirošanas algoritmiem.

kausa šķirošana

Beidzot, pulcēties sakārtotos elementus no katra spaiņa secībā

kausa šķirošana

Tagad masīvs ir pilnībā sakārtots.

Kausu kārtošanas sarežģītība

Tagad apskatīsim segmenta kārtošanas laika sarežģītību labākajā, vidējā un sliktākajā gadījumā. Mēs redzēsim arī kausa šķirošanas telpas sarežģītību.

1. Laika sarežģītība

Lieta Laiks Sarežģītība
Labākais gadījums O(n+k)
Vidējais gadījums O(n+k)
Sliktākajā gadījumā O(n2)
    Labākā gadījuma sarežģītība —Tas notiek, ja nav nepieciešama šķirošana, t.i., masīvs jau ir sakārtots. Segu kārtošanā labākais gadījums notiek, ja elementi segmentos ir vienmērīgi sadalīti. Sarežģītība būs labāka, ja elementi jau būs sakārtoti spainī.
    Ja mēs izmantojam ievietošanas kārtošanu, lai kārtotu kausa elementus, kopējā sarežģītība būs lineāra, t.i., O(n + k), kur O(n) ir kausu veidošanai, bet O(k) ir kausa elementu kārtošanai. labākajā gadījumā izmantojot algoritmus ar lineāru laika sarežģītību.
    Labākā gadījuma laika sarežģītība kausa kārtošanai ir O(n+k) .Vidējā gadījuma sarežģītība —Tas notiek, ja masīva elementi ir sajauktā secībā, kas nav pareizi augoša un nepareizi dilstoša. Kausu kārtošana notiek lineārā laikā, pat ja elementi ir vienmērīgi sadalīti. Vidējā gadījuma laika sarežģītība kausa kārtošanā ir O(n+K) .Sliktākā gadījuma sarežģītība -Kausu kārtošanā sliktākais gadījums notiek, kad elementi masīvā atrodas tuvu diapazonam, tāpēc tie ir jāievieto vienā segmentā. Tātad dažiem spaiņiem ir vairāk elementu nekā citos.
    Sarežģītība pasliktināsies, ja elementi būs apgrieztā secībā.
    Sliktākā gadījuma laika sarežģītība spainī ir O(n2) .

2. Telpas sarežģītība

Kosmosa sarežģītība O(n*k)
Stabils JĀ
  • Kausa kārtošanas telpas sarežģītība ir O(n*k).

Kausu šķirošanas ieviešana

Tagad apskatīsim kausa kārtošanas programmas dažādās programmēšanas valodās.

Programma: Uzrakstiet programmu spaiņu kārtošanai C valodā.

 #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></=>