Tässä artikkelissa käsittelemme ämpärilajittelualgoritmia. Ryhmälajittelun tietokohteet jaetaan ämpärien muodossa. Ohjelmistoinsinöörien koodaus- tai teknisissä haastatteluissa lajittelualgoritmeja kysytään laajalti. Joten on tärkeää keskustella aiheesta.
Sämpärilajittelu on lajittelualgoritmi, joka jakaa elementit useisiin ryhmiin, joiden sanotaan olevan ämpäri. Sämpärilajittelun elementit jaetaan ensin tasaisesti ryhmiin, joita kutsutaan ryhmiksi, ja sitten ne lajitellaan millä tahansa muulla lajittelualgoritmilla. Sen jälkeen elementit kootaan lajiteltuna.
Ämpärilajittelun suorittamisen perusmenettely esitetään seuraavasti:
- Ensin osioita alue kiinteään määrään ryhmiä.
- Heitä sitten jokainen elementti sopivaan ämpäriinsä.
- Lajittele sen jälkeen kukin segmentti erikseen käyttämällä lajittelualgoritmia.
- Ja lopuksi ketjuta kaikki lajitellut kauhat.
Kauhalajittelun edut ovat -
- Kauhan lajittelu vähentää no. vertailuista.
- Se on asymptoottisen nopea alkuaineiden tasaisen jakautumisen vuoksi.
Kauhan lajittelun rajoitukset ovat -
- Se voi olla vakaa lajittelualgoritmi tai ei.
- Ei ole hyödyllistä, jos meillä on suuri joukko, koska se lisää kustannuksia.
- Se ei ole paikan päällä oleva lajittelualgoritmi, koska ämpärien lajittelu vaatii ylimääräistä tilaa.
Kauhan lajittelun paras ja keskimääräinen monimutkaisuus on O(n + k) , ja ämpärilajittelun pahin monimutkaisuus on Päällä2) , missä n on kohteiden lukumäärä.
Kauhalajittelu on yleisesti käytetty -
- Liukulukuarvoilla.
- Kun tulo on jakautunut tasaisesti alueelle.
Perusidea ämpärilajittelun suorittamiseen annetaan seuraavasti -
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
Katsotaan nyt ämpärilajittelun algoritmia.
Algoritmi
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
Haja-kerää-lähestymistapa
Pystymme ymmärtämään ämpärilajittelualgoritmin sironta-keräysmenetelmällä. Tässä annetut elementit hajallaan ensin ämpäriin. Sirotuksen jälkeen kunkin sängyn elementit lajitellaan vakaalla lajittelualgoritmilla. Viimeinkin lajitellut elementit kootaan järjestykseen.
Otetaan lajittelematon taulukko ymmärtääksemme ämpärilajitteluprosessin. Ämpärilajittelu on helpompi ymmärtää esimerkin avulla.
Olkoon taulukon elementit -
Luo nyt ämpärit, joiden alue on 0-25. Säilöjen alueet ovat 0-5, 5-10, 10-15, 15-20, 20-25. Elementit asetetaan kauhoihin kauhavalikoiman mukaan. Oletetaan, että kohteen arvo on 16, joten se lisätään alueeseen 15-20. Samoin jokainen taulukon kohde lisätään vastaavasti.
Tämän vaiheen tiedetään olevan taulukon elementtien sironta .
Nyt, järjestellä jokainen ämpäri erikseen. Kunkin segmentin elementit voidaan lajitella käyttämällä mitä tahansa stabiilia lajittelualgoritmia.
Viimeinkin, kerätä lajitellut elementit kustakin ryhmästä järjestyksessä
Nyt matriisi on täysin lajiteltu.
Kauhan lajittelun monimutkaisuus
Katsotaan nyt ämpärilajittelun aikamonimutkaisuus parhaassa tapauksessa, keskimääräisessä tapauksessa ja pahimmassa tapauksessa. Näemme myös ämpärilajittelun tilan monimutkaisuuden.
1. Aika monimutkaisuus
| Asia | Aika | Monimutkaisuus |
|---|---|---|
| Paras tapaus | O(n + k) | |
| Keskimääräinen tapaus | O(n + k) | |
| Pahimmassa tapauksessa | Päällä2) |
Jos käytämme lisäyslajittelua kauhan elementtien lajitteluun, kokonaismonimutkaisuus on lineaarinen, eli O(n + k), missä O(n) on kauhojen tekemiseen ja O(k) on kauhan elementtien lajitteluun. käyttämällä parhaimmassa tapauksessa lineaarisen aikamonimutkaisuuden algoritmeja.
Parhaassa tapauksessa ämpärilajittelun aikamonimutkaisuus on O(n + k) .
Monimutkaisuus pahenee, kun elementit ovat päinvastaisessa järjestyksessä.
Ämpärilajittelun pahin aika monimutkaisuus on Päällä2) .
2. Tilan monimutkaisuus
| Avaruuden monimutkaisuus | O(n*k) |
| Vakaa | JOO |
- Ämpärilajittelun tilamonimutkaisuus on O(n*k).
Kauhalajittelun toteutus
Katsotaanpa nyt ämpärilajiteltuja ohjelmia eri ohjelmointikielillä.
Ohjelmoida: Kirjoita ohjelma, joka toteuttaa ämpärilajittelun C-kielellä.
#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'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></=>