logo

TechCodeview

Algoritem za razvrščanje vedra

V tem članku bomo razpravljali o algoritmu za razvrščanje vedra. Podatkovne postavke v razvrščanju veder so porazdeljene v obliki veder. V kodirnih ali tehničnih intervjujih za programske inženirje se veliko sprašuje o algoritmih razvrščanja. Zato je pomembno razpravljati o temi.

Bucket sort je algoritem za razvrščanje, ki loči elemente v več skupin, imenovanih vedra. Elementi pri razvrščanju po vedrih so najprej enotno razdeljeni v skupine, imenovane vedra, nato pa so razvrščeni s katerim koli drugim algoritmom za razvrščanje. Po tem se elementi zberejo razvrščeno.

Osnovni postopek izvajanja razvrščanja vedra je podan na naslednji način -

  • Najprej razdelite obseg na določeno število veder.
  • Nato vsak element vrzite v ustrezno vedro.
  • Nato razvrstite vsako vedro posebej z uporabo algoritma za razvrščanje.
  • In končno združite vsa razvrščena vedra.

Prednosti sortiranja z vedro so:

  • Bucket sort zmanjša št. primerjav.
  • Je asimptotično hiter zaradi enakomerne porazdelitve elementov.

Omejitve razvrščanja vedra so -

  • Lahko je stabilen algoritem za razvrščanje ali pa tudi ne.
  • Ni uporabno, če imamo veliko polje, ker poveča stroške.
  • To ni algoritem za razvrščanje na mestu, ker je za razvrščanje veder potrebno nekaj dodatnega prostora.

Najboljša in povprečna zapletenost razvrščanja vedra je O(n + k) , in najslabša zapletenost razvrščanja vedra je O(n2) , kje n je število predmetov.

Običajno se uporablja vrsta vedra -

  • Z vrednostmi v plavajoči vejici.
  • Ko je vnos enakomerno porazdeljen po območju.

Osnovna ideja za izvedbo razvrščanja vedra je podana na naslednji način -

 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

Zdaj pa poglejmo algoritem razvrščanja vedra.

Algoritem

 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

Pristop razpršitve

Algoritem razvrščanja Bucket lahko razumemo s pristopom razpršenega zbiranja. Tukaj so dani elementi najprej razpršeni v vedra. Po razpršitvi so elementi v vsakem vedru razvrščeni z uporabo stabilnega algoritma za razvrščanje. Končno bodo razvrščeni elementi zbrani po vrstnem redu.

Vzemimo nerazvrščeno matriko, da razumemo postopek razvrščanja vedra. Razvrščanje vedra bo lažje razumeti na primeru.

Naj so elementi matrike -

vrsta vedra

Zdaj ustvarite vedra z razponom od 0 do 25. Razponi veder so 0-5, 5-10, 10-15, 15-20, 20-25. Elementi se vstavljajo v vedra glede na obseg žlic. Recimo, da je vrednost predmeta 16, tako da bo vstavljen v vedro z obsegom 15–20. Podobno se bo vsak element matrike ustrezno vstavil.

Ta faza je znana kot razpršenost elementov niza .

vrsta vedra

zdaj, vrsta vsako vedro posebej. Elemente vsakega vedra je mogoče razvrstiti z uporabo katerega koli od stabilnih algoritmov za razvrščanje.

vrsta vedra

Končno, zbrati razvrščene elemente iz vsakega vedra po vrstnem redu

vrsta vedra

Sedaj je niz popolnoma urejen.

Zapletenost razvrščanja vedra

Zdaj pa poglejmo časovno zahtevnost razvrščanja vedra v najboljšem, povprečnem primeru in v najslabšem primeru. Videli bomo tudi prostorsko zapletenost vrste vedra.

1. Časovna zapletenost

Ovitek Čas Kompleksnost
Najboljši primer O(n + k)
Povprečen primer O(n + k)
V najslabšem primeru O(n2)
    Najboljša zapletenost -Pojavi se, ko razvrščanje ni potrebno, tj. matrika je že razvrščena. Pri razvrščanju po vedrih je najboljši primer, ko so elementi enakomerno porazdeljeni v vedrih. Kompleksnost bo boljša, če so elementi že razvrščeni v vedra.
    Če za razvrščanje elementov vedra uporabimo razvrščanje z vstavljanjem, bo celotna kompleksnost linearna, tj. O(n + k), kjer je O(n) za izdelavo veder, O(k) pa za razvrščanje elementov vedra z uporabo algoritmov z linearno časovno kompleksnostjo v najboljšem primeru.
    Najboljši primer časovne zapletenosti razvrščanja vedra je O(n + k) .Povprečna zapletenost primera -Pojavi se, ko so elementi niza v zmešanem vrstnem redu, ki ni pravilno naraščajoče in ni pravilno padajoče. Bucket sortiranje teče v linearnem času, tudi če so elementi enakomerno porazdeljeni. Povprečna časovna zapletenost primera razvrščanja vedra je O(n + K) .Kompleksnost v najslabšem primeru -Pri razvrščanju vedra se najslabši primer zgodi, ko so elementi v nizu blizu, zato jih je treba postaviti v isto vedro. Torej imajo nekatera vedra več elementov kot druga.
    Kompleksnost se bo poslabšala, če bodo elementi v obratnem vrstnem redu.
    Najslabša časovna zapletenost razvrščanja vedra je O(n2) .

2. Kompleksnost prostora

Kompleksnost prostora O(n*k)
Stabilen DA
  • Prostorska kompleksnost razvrščanja vedra je O(n*k).

Izvedba bucket sort

Zdaj pa si oglejmo programe za razvrščanje veder v različnih programskih jezikih.

Program: Napišite program za implementacijo razvrščanja vedra v jeziku 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></=>