logo

TechCodeview

Rūšiavimo pagal kaušą algoritmas

Šiame straipsnyje aptarsime kibirų rūšiavimo algoritmą. Segmentų rūšiavimo duomenų elementai paskirstomi segmentų pavidalu. Kodavimo ar techninių pokalbių programinės įrangos inžinieriams metu plačiai klausiama rūšiavimo algoritmų. Taigi, svarbu aptarti temą.

Rūšiavimas į segmentus yra rūšiavimo algoritmas, kuris suskirsto elementus į kelias grupes, kurios laikomos segmentais. Elementai rūšiuojant segmentus pirmiausia vienodai suskirstomi į grupes, vadinamas segmentais, o tada rūšiuojami pagal bet kurį kitą rūšiavimo algoritmą. Po to elementai surenkami rūšiuotu būdu.

Pagrindinė rūšiavimo į kaušą atlikimo procedūra pateikiama taip:

  • Pirma, padalinkite diapazoną į fiksuotą skaičių segmentų.
  • Tada sumeskite kiekvieną elementą į atitinkamą kibirą.
  • Po to surūšiuokite kiekvieną kibirą atskirai, taikydami rūšiavimo algoritmą.
  • Ir pagaliau sujunkite visus surūšiuotus kibirus.

Kaušo rūšiavimo pranašumai yra šie:

  • Kaušo rūšiavimas sumažina Nr. palyginimų.
  • Jis yra asimptotiškai greitas dėl vienodo elementų pasiskirstymo.

Kaušo rūšiavimo apribojimai yra:

  • Tai gali būti stabilus rūšiavimo algoritmas arba ne.
  • Nenaudinga, jei turime didelį masyvą, nes tai padidina išlaidas.
  • Tai nėra rūšiavimo vietoje algoritmas, nes norint surūšiuoti kibirus reikia papildomos vietos.

Geriausias ir vidutinis kaušų rūšiavimo sudėtingumas yra O(n + k) , o rūšiavimo kibirais sudėtingiausias atvejis yra O (n2) , kur n yra elementų skaičius.

Paprastai naudojamas kaušų rūšiavimas -

  • Su slankiojo kablelio reikšmėmis.
  • Kai įvestis yra tolygiai paskirstyta diapazone.

Pagrindinė idėja rūšiuoti kibirą pateikiama taip:

 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

Dabar pažiūrėkime į kaušelio rūšiavimo algoritmą.

Algoritmas

 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“ metodas

Mes galime suprasti segmento rūšiavimo algoritmą naudodami išsklaidymo ir rinkimo metodą. Čia duoti elementai pirmiausia išbarstomi į kibirus. Išsklaidę elementai kiekviename segmente surūšiuojami naudojant stabilų rūšiavimo algoritmą. Pagaliau surūšiuoti elementai bus surinkti eilės tvarka.

Paimkime nerūšiuotą masyvą, kad suprastume rūšiavimo į segmentus procesą. Pagal pavyzdį bus lengviau suprasti kibirų rūšiavimą.

Tegul masyvo elementai yra -

rūšiuoti kibirą

Dabar kurkite segmentus, kurių diapazonas yra nuo 0 iki 25. Segmentų diapazonas yra 0–5, 5–10, 10–15, 15–20, 20–25. Elementai į kibirus įdedami pagal kaušų asortimentą. Tarkime, kad elemento vertė yra 16, taigi jis bus įterptas į segmentą, kurio diapazonas yra 15–20. Panašiai kiekvienas masyvo elementas bus atitinkamai įterptas.

Yra žinoma, kad ši fazė yra masyvo elementų sklaida .

rūšiuoti kibirą

Dabar rūšiuoti kiekvienas kibiras atskirai. Kiekvieno segmento elementus galima rūšiuoti naudojant bet kurį stabilų rūšiavimo algoritmą.

rūšiuoti kibirą

Pagaliau, rinkti surūšiuoti elementai iš kiekvieno kibiro eilės tvarka

rūšiuoti kibirą

Dabar masyvas yra visiškai surūšiuotas.

Kaušo rūšiavimo sudėtingumas

Dabar pažiūrėkime, kiek laiko sudėtinga rūšiuoti kibirą geriausiu, vidutiniu ir blogiausiu atveju. Taip pat pamatysime kaušų rūšiavimo erdvės sudėtingumą.

1. Laiko sudėtingumas

Byla Laikas Sudėtingumas
Geriausias atvejis O(n + k)
Vidutinis atvejis O(n + k)
Blogiausiu atveju O (n2)
    Geriausio atvejo sudėtingumas –Tai atsitinka, kai nereikia rūšiuoti, ty masyvas jau surūšiuotas. Rūšiuojant į segmentus geriausias atvejis įvyksta, kai elementai yra tolygiai paskirstyti kibiruose. Sudėtingumas bus geresnis, jei elementai jau bus surūšiuoti kibiruose.
    Jei naudosime įterpimo rūšiavimą segmento elementams rūšiuoti, bendras sudėtingumas bus linijinis, t. y. O(n + k), kur O(n) – segmentų rūšiavimui, o O(k) – segmento elementų rūšiavimui. geriausiu atveju naudojant linijinio laiko sudėtingumo algoritmus.
    Geriausiu atveju rūšiavimo pagal laiką sudėtingumas yra O(n + k) .Vidutinis atvejo sudėtingumas –Tai atsitinka, kai masyvo elementai yra sumaišyti, o tai netinkamai kyla ir netinkamai mažėja. Rūšiavimas pagal segmentus vykdomas linijiniu laiku, net kai elementai yra tolygiai paskirstyti. Vidutinis segmentų rūšiavimo sudėtingumas yra O(n + K) .Blogiausio atvejo sudėtingumas –Rūšiuojant kibirą, blogiausias atvejis būna tada, kai elementai masyve yra artimo diapazono, dėl to jie turi būti dedami į tą patį segmentą. Taigi, kai kurie kaušai turi daugiau elementų nei kiti.
    Sudėtingumas padidės, kai elementai bus išdėstyti atvirkštine tvarka.
    Blogiausiu atveju rūšiavimo kibirais sudėtingumas yra O (n2) .

2. Erdvės sudėtingumas

Erdvės sudėtingumas O(n*k)
Stabilus TAIP
  • Kaušelio rūšiavimo erdvės sudėtingumas yra O(n*k).

Kaušų rūšiavimo įgyvendinimas

Dabar pažiūrėkime, kaip skirtingomis programavimo kalbomis surūšiuotos programos.

Programa: Parašykite programą, skirtą C kalba įdiegti bucket sort.

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