In diesem Artikel besprechen wir den Bucket-Sort-Algorithmus. Die Datenelemente in der Bucket-Sortierung werden in Form von Buckets verteilt. In Codierungs- oder technischen Interviews für Softwareentwickler werden Sortieralgorithmen häufig gefragt. Daher ist es wichtig, das Thema zu diskutieren.
Bei der Bucket-Sortierung handelt es sich um einen Sortieralgorithmus, der die Elemente in mehrere Gruppen, sogenannte Buckets, aufteilt. Elemente bei der Bucket-Sortierung werden zunächst einheitlich in Gruppen, sogenannte Buckets, unterteilt und dann mit einem beliebigen anderen Sortieralgorithmus sortiert. Danach werden die Elemente sortiert gesammelt.
Das grundlegende Verfahren zur Durchführung der Bucket-Sortierung ist wie folgt:
- Teilen Sie zunächst den Bereich in eine feste Anzahl von Buckets auf.
- Werfen Sie dann jedes Element in den entsprechenden Eimer.
- Sortieren Sie anschließend jeden Bucket einzeln, indem Sie einen Sortieralgorithmus anwenden.
- Und schließlich verketten Sie alle sortierten Buckets.
Die Vorteile der Eimersortierung sind:
- Bucket-Sortierung reduziert die Anzahl. von Vergleichen.
- Aufgrund der gleichmäßigen Verteilung der Elemente ist es asymptotisch schnell.
Die Einschränkungen der Bucket-Sortierung sind:
- Es kann ein stabiler Sortieralgorithmus sein oder auch nicht.
- Es ist nicht sinnvoll, wenn wir über ein großes Array verfügen, da es die Kosten erhöht.
- Es handelt sich nicht um einen In-Place-Sortieralgorithmus, da zum Sortieren der Buckets etwas zusätzlicher Platz erforderlich ist.
Die beste und durchschnittliche Komplexität der Bucket-Sortierung beträgt O(n + k) und die Worst-Case-Komplexität der Bucket-Sortierung ist An2) , Wo N ist die Anzahl der Artikel.
Die Bucket-Sortierung wird häufig verwendet -
- Mit Gleitkommawerten.
- Wenn die Eingabe gleichmäßig über einen Bereich verteilt ist.
Die Grundidee zur Durchführung der Bucket-Sortierung ist wie folgt:
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
Sehen wir uns nun den Algorithmus der Bucket-Sortierung an.
Algorithmus
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-Ansatz
Wir können den Bucket-Sortieralgorithmus über den Scatter-Gather-Ansatz verstehen. Dabei werden die vorgegebenen Elemente zunächst in Eimer gestreut. Nach der Streuung werden die Elemente in jedem Bucket mithilfe eines stabilen Sortieralgorithmus sortiert. Zuletzt werden die sortierten Elemente der Reihe nach zusammengestellt.
Nehmen wir ein unsortiertes Array, um den Prozess der Bucket-Sortierung zu verstehen. Anhand eines Beispiels lässt sich die Bucket-Sortierung leichter verstehen.
Die Elemente des Arrays seien -
Erstellen Sie nun Buckets mit einem Bereich von 0 bis 25. Der Bucket-Bereich ist 0–5, 5–10, 10–15, 15–20, 20–25. Elemente werden entsprechend dem Bucket-Bereich in die Buckets eingefügt. Angenommen, der Wert eines Elements beträgt 16, sodass es im Bereich 15–20 in den Bucket eingefügt wird. Ebenso wird jedes Element des Arrays entsprechend eingefügt.
Diese Phase ist bekanntermaßen die Streuung von Array-Elementen .
Jetzt, Sortieren jeden Eimer einzeln. Die Elemente jedes Buckets können mithilfe eines beliebigen stabilen Sortieralgorithmus sortiert werden.
Zu guter Letzt, versammeln die sortierten Elemente aus jedem Bucket der Reihe nach
Jetzt ist das Array vollständig sortiert.
Komplexität der Bucket-Sortierung
Sehen wir uns nun die zeitliche Komplexität der Bucket-Sortierung im besten Fall, im Durchschnittsfall und im schlechtesten Fall an. Wir werden auch die räumliche Komplexität der Bucket-Sortierung sehen.
1. Zeitkomplexität
| Fall | Zeit | Komplexität |
|---|---|---|
| I'm besten fall | O(n + k) | |
| Durchschnittlicher Fall | O(n + k) | |
| Schlimmsten Fall | An2) |
Wenn wir die Einfügungssortierung verwenden, um die Bucket-Elemente zu sortieren, ist die Gesamtkomplexität linear, d. h. O(n + k), wobei O(n) für die Erstellung der Buckets und O(k) für die Sortierung der Bucket-Elemente dient Verwendung von Algorithmen mit linearer Zeitkomplexität im besten Fall.
Die zeitliche Komplexität der Bucket-Sortierung beträgt im besten Fall O(n + k) .
Die Komplexität wird noch schlimmer, wenn die Elemente in umgekehrter Reihenfolge vorliegen.
Die zeitliche Komplexität der Bucket-Sortierung beträgt im schlimmsten Fall An2) .
2. Raumkomplexität
| Weltraumkomplexität | O(n*k) |
| Stabil | JA |
- Die räumliche Komplexität der Bucket-Sortierung beträgt O(n*k).
Implementierung der Bucket-Sortierung
Sehen wir uns nun die Programme der Bucket-Sortierung in verschiedenen Programmiersprachen an.
Programm: Schreiben Sie ein Programm zur Implementierung der Bucket-Sortierung in der Sprache 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'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></=>