logo

TechCodeview

Algoritam za sortiranje spremnika

U ovom ćemo članku raspravljati o algoritmu sortiranja kante. Podatkovne stavke u sortiranju spremnika raspoređene su u obliku spremnika. U programskim ili tehničkim intervjuima za softverske inženjere često se postavljaju pitanja o algoritmima sortiranja. Dakle, važno je razgovarati o temi.

Bucket sort je algoritam za sortiranje koji razdvaja elemente u više grupa za koje se kaže da su segmenti. Elementi u bucket sortiranju prvo se ravnomjerno dijele u skupine koje se nazivaju bucket, a zatim se sortiraju bilo kojim drugim algoritmom sortiranja. Nakon toga se elementi skupljaju sortirani.

Osnovni postupak izvođenja bucket sortiranja dan je kako slijedi -

  • Prvo podijelite raspon u fiksni broj spremnika.
  • Zatim bacite svaki element u odgovarajuću kantu.
  • Nakon toga sortirajte svaku kantu pojedinačno primjenom algoritma sortiranja.
  • I na kraju, spojite sve sortirane kante.

Prednosti bucket sortiranja su -

  • Bucket sortiranje smanjuje br. usporedbi.
  • Asimptotski je brz zbog jednolike raspodjele elemenata.

Ograničenja sortiranja spremnika su -

  • Može, ali i ne mora biti stabilan algoritam sortiranja.
  • Nije korisno ako imamo veliki niz jer povećava trošak.
  • To nije algoritam za sortiranje na mjestu, jer je potreban dodatni prostor za sortiranje spremnika.

Najbolja i prosječna složenost bucket sortiranja je O(n + k) , a složenost bucket sortiranja u najgorem slučaju je Na2) , gdje n je broj stavki.

Uobičajeno se koristi sortiranje kante -

  • S vrijednostima u pokretnom zarezu.
  • Kada je unos ravnomjerno raspoređen u rasponu.

Osnovna ideja za izvođenje bucket sortiranja dana je kako slijedi -

 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

Sada, da vidimo algoritam bucket sortiranja.

Algoritam

 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

Pristup raspršivanja

Algoritam Bucket sortiranja možemo razumjeti putem raspršenog pristupa. Ovdje se dani elementi prvo raspršuju u kante. Nakon raspršivanja, elementi u svakoj kanti se sortiraju pomoću stabilnog algoritma sortiranja. Napokon će sortirani elementi biti sakupljeni po redu.

Uzmimo nesortirani niz da bismo razumjeli proces sortiranja u segmente. Lakše ćete razumjeti sortiranje kante na primjeru.

Neka su elementi niza -

vrsta kante

Sada stvorite kante s rasponom od 0 do 25. Rasponi kanti su 0-5, 5-10, 10-15, 15-20, 20-25. Elementi se ubacuju u žlice prema rasponu žlica. Pretpostavimo da je vrijednost stavke 16, pa će biti umetnuta u kantu s rasponom 15-20. Slično će se svaka stavka niza umetnuti u skladu s tim.

Poznato je da je ova faza raspršenost elemenata niza .

vrsta kante

Sada, vrsta svaku kantu pojedinačno. Elementi svake kante mogu se sortirati korištenjem bilo kojeg stabilnog algoritma sortiranja.

vrsta kante

Napokon, skupiti se poredane elemente iz svake kante redom

vrsta kante

Sada je niz potpuno sortiran.

Složenost sortiranja kante

Sada, da vidimo vremensku složenost sortiranja kante u najboljem slučaju, prosječnom slučaju iu najgorem slučaju. Također ćemo vidjeti složenost prostora sortiranja žlica.

1. Vremenska složenost

Slučaj Vrijeme Složenost
Najbolji slučaj O(n + k)
Prosječan slučaj O(n + k)
Najgori slučaj Na2)
    Složenost u najboljem slučaju -To se događa kada nije potrebno sortiranje, tj. niz je već sortiran. U Bucket sortiranju, najbolji slučaj se događa kada su elementi ravnomjerno raspoređeni u korpama. Složenost će biti bolja ako su elementi već poredani u spremnicima.
    Ako koristimo sortiranje umetanjem za sortiranje elemenata spremnika, ukupna će složenost biti linearna, tj. O(n + k), gdje je O(n) za izradu spremnika, a O(k) za sortiranje elemenata spremnika koristeći algoritme s linearnom vremenskom složenošću u najboljem slučaju.
    Najbolja vremenska složenost bucket sortiranja je O(n + k) .Prosječna složenost slučaja -To se događa kada su elementi niza u zbrkanom redoslijedu koji nije ispravno uzlazan i nije ispravno silazni. Bucket sortiranje radi u linearnom vremenu, čak i kada su elementi ravnomjerno raspoređeni. Prosječna složenost slučaja bucket sortiranja je O(n + K) .Složenost u najgorem slučaju -Kod bucket sortiranja, najgori slučaj se događa kada su elementi blizu niza, zbog toga moraju biti smješteni u isti bucket. Dakle, neke kante imaju veći broj elemenata od drugih.
    Složenost će se pogoršati kada su elementi u obrnutom redoslijedu.
    Vremenska složenost bucket sortiranja u najgorem slučaju je Na2) .

2. Složenost prostora

Složenost prostora O(n*k)
Stabilan DA
  • Prostorna složenost bucket sortiranja je O(n*k).

Implementacija bucket sortiranja

Sada, pogledajmo programe bucket sortiranja u različitim programskim jezicima.

Program: Napišite program za implementaciju bucket sortiranja u C jeziku.

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