Bucket-Sort-Algorithmus (Java, Python, C/C++ Codebeispiele)
Sarah Chen
Was ist Bucket Sort?
Bucket-Sortierung, oft auch Bin-Sortierung genannt, ist eine Vergleichssortiermethode, die ein unsortiertes Array als Eingabe akzeptiert und als Ergebnis ein sortiertes Array erzeugt. Bei dieser Methode werden die Elemente auf mehrere Buckets verteilt und jeder dieser Buckets einzeln nach einem beliebigen Sortieralgorithmus wie der Einfügungssortierung sortiert. Anschließend werden alle Buckets zu einem sortierten Array zusammengeführt.
Bucket-Sortierung wird häufig verwendet, wenn die Elemente-
- Gleitkommawerte
- Gleichmäßig über einen Bereich verteilt
Die zeitliche Komplexität von Bucketsort hängt von der Anzahl der verwendeten Buckets und der Einheitlichkeit der Eingabeverteilung ab. Während verschiedene Sortieralgorithmen wie Muschelsortierung, Zusammenführungssortierung, Heapsortierung und schnelle Sorte kann im besten Fall eine Zeitkomplexität von O(n*logn) erreichen, der Bucket-Sortierungsalgorithmus kann dasselbe mit einer linearen Zeitkomplexität von O(n) erreichen.
Bucketsortierung folgt dem Scatter-Gather-Ansatz. Bei diesem Ansatz werden die Elemente in die entsprechenden Buckets gestreut, in den Buckets sortiert und im letzten Schritt zu einem sortierten Array zusammengefasst. Dieser Scatter-Gather-Ansatz wird im folgenden Abschnitt erläutert.
Scatter-Gather-Ansatz
Große, komplexe Probleme können manchmal schwierig zu lösen sein. Der Scatter-Gather-Ansatz versucht, solche Probleme zu lösen, indem er den gesamten Datensatz in Cluster unterteilt. Dann wird jeder Cluster einzeln behandelt und alles wieder zusammengeführt, um die endgültige Antwort zu erhalten.
So implementiert der Bucket-Sortieralgorithmus die Scatter-Gather-Methode:
So funktioniert Bucket Sort
Das grundlegende Funktionsprinzip der Bucket-Sortierung ist wie folgt:
- Es wird eine Reihe leerer Buckets erstellt. Aufgrund unterschiedlicher Richtlinien kann die Anzahl der Buckets unterschiedlich sein.
- Platzieren Sie jedes Element aus dem Eingabearray in seinem entsprechenden Bucket.
- Sortieren Sie diese Eimer einzeln.
- Verketten Sie die sortierten Buckets, um ein einzelnes Ausgabearray zu erstellen.
Die detaillierten Arbeitsschritte werden in den folgenden Abschnitten beschrieben.
Pseudocode
Start Create N empty buckets For each array element: Calculate bucket index Put that element into the corresponding bucket For each bucket: Sort elements within each bucket Merge all the elements from each bucket Output the sorted array End
Methode 1: Bucket-Sortieralgorithmus für Gleitkomma Numbers
Der Bucket-Sortierungsalgorithmus für Gleitkommazahlen im Bereich von 0.0 bis 1.0:
Schritt 1) Erstellen Sie zehn (10) leere Buckets, sodass der erste Bucket Zahlen im Bereich [0.0; 0.1] enthält. Der zweite Bucket enthält dann Zahlen im Bereich [0.1; 0.2] und so weiter.
Schritt 2) Für jedes Array-Element:
-
A. Berechnen Sie den Bucket-Index mit der Formel:
Bucket-Index= no_of_buckets *array_element
-
B. Fügen Sie das Element in den Bucket ein[bucket_index]
Schritt 3) Sortieren Sie jeden Eimer einzeln mithilfe der Einfügungssortierung.
Schritt 4) Verketten Sie alle Buckets in einem einzigen Array.
Sehen wir uns ein Bucket-Sort-Beispiel an. Für dieses Beispiel sortieren wir das folgende Array mit dem Bucket-Sort-Algorithmus:
Schritt 1) Zuerst erstellen wir 10 leere Buckets. Der erste Bucket enthält die Zahlen zwischen [0.0, 0.1). Der zweite Bucket enthält dann die Zahlen zwischen [0.1, 0.2) und so weiter.
Schritt 2) Für jedes Array-Element berechnen wir den Bucket-Index und platzieren das Element in diesem Bucket.
Der Bucket-Index kann mit der Formel berechnet werden:
Bucket_index= no_of_buckets*array_element
Berechnung des Bucket-Index:
a) 0.78
Bucket_index = no_of_buckets*array_element
= 10 * 0.78
= 7.8
Daher wird das Element 0.78 auf dem Bucket[Boden(7.8)] oder dem Bucket[7] gespeichert.
b) 0.17
Bucket_index = no_of_buckets * Array-Element
= 10 * 0.17
= 1.7
Das Array-Element 0.17 wird auf Bucket[floor(1.7)] oder Bucket[1] gespeichert.
c) 0.39
Bucket_index = no_of_buckets * Array-Element
= 10 * 0.39
= 3.9
0.39 werden auf Bucket[Boden(3.9)] oder Bucket[3] gespeichert.
Nach der Iteration über alle Array-Elemente lauten die Buckets wie folgt:
Schritt 3) Anschließend wird jeder Bucket mithilfe der Insertionsortierung sortiert. Nach dem Sortiervorgang lautet die Ausgabe:
Schritt 4) Im letzten Schritt werden die Buckets zu einem einzigen Array verkettet. Dieses Array ist das sortierte Ergebnis der Eingabe.
Jeder Bucket wird mit dem Ausgabearray verkettet. Zum Beispiel die Verkettung der zweiten Bucket-Elemente:
Die Verkettung der letzten Bucket-Elemente sieht wie folgt aus:
Nach der Verkettung ist das resultierende Array das gewünschte sortierte Array.
Bucket-Sort-Programm in C/C++
Eingang:
//Bucket Sort Program in C/C++
//For not having integer parts
#include <bits/stdc++.h>
#define BUCKET_SIZE 10
using namespace std;
void bucketSort(float input[], int array_size)
{
vector <float>bucket[BUCKET_SIZE];
for (int i = 0; i < array_size; i++) {
int index = BUCKET_SIZE*input[i];
bucket[index].push_back(input[i]);
}
for (int i = 0; i < BUCKET_SIZE; i++)
sort(bucket[i].begin(), bucket[i].end());
int out_index = 0;
for (int i = 0; i < BUCKET_SIZE; i++)
for (int j = 0; j < bucket[i].size(); j++)
input[out_index++] = bucket[i][j];
}
int main()
{
float input[]={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.69};
int array_size = sizeof(input)/sizeof(input[0]);
bucketSort(input, array_size);
cout <<"Sorted Output: \n";
for (int i = 0; i< array_size; i++)
cout<<input[i]<<" ";
return 0;
}
Ausgang:
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
Bucket-Sort-Programm in Python
Eingang:
# Bucket Sort Program in Python
# For not having integer parts
def bucketSort(input):
output = []
bucket_size = 10
for bucket in range(bucket_size):
output.append([])
for element in input:
index = int(bucket_size * element)
output[index].append(element)
for bucket in range(bucket_size):
output[bucket] = sorted(output[bucket])
out_index = 0
for bucket in range(bucket_size):
for element in range(len(output[bucket])):
input[out_index] = output[bucket][element]
out_index += 1
return input
input = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.69]
print("Sorted Output:")
print(bucketSort(input))
Ausgang:
Sorted Output: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.69, 0.72, 0.78, 0.94]
Bucket-Sortierung in Java
Eingang:
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
private static final int BUCKET_SIZE = 10;
public static void bucketSort(float[] input, int arraySize) {
List <
Float >
[] bucket = new ArrayList[BUCKET_SIZE];
for (int i = 0; i < arraySize; i++) {
int index = (int)(BUCKET_SIZE * input[i]);
if (bucket[index] == null) {
bucket[index] = new ArrayList < >
();
}
bucket[index].add(input[i]);
}
for (int i = 0; i < BUCKET_SIZE; i++) {
if (bucket[i] != null) {
Collections.sort(bucket[i]);
}
}
int outIndex = 0;
for (int i = 0; i < BUCKET_SIZE; i++) {
if (bucket[i] != null) {
for (float value: bucket[i]) {
input[outIndex++] = value;
}
}
}
}
public static void main(String[] args) {
float[] input = {0.78f,0.17f,0.39f,0.26f,0.72f,0.94f,0.21f,0.12f,0.23f,0.69f};
int arraySize = input.length;
bucketSort(input, arraySize);
System.out.println("Sorted Output:");
for (int i = 0; i < arraySize; i++) {
System.out.print(input[i]+" ");
}
}
}
Ausgang:
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
Methode 2: Bucket-Sortieralgorithmus für ganzzahlige Elemente
Der Bucket-Sort-Algorithmus für die Eingabe, die Zahlen außerhalb des Bereichs [0.0, 1.0] enthält, unterscheidet sich ein wenig vom vorherigen Algorithmus. Die für diesen Fall erforderlichen Schritte sind wie folgt:
Schritt 1) Finden Sie die maximalen und minimalen Elemente.
Schritt 2) Wählen Sie die Anzahl der Buckets (n) aus und initialisieren Sie diese Buckets als leer.
Schritt 3) Berechnen Sie die Reichweite oder Spanne jedes Buckets mithilfe der Formel:
span = (maximum - minimum)/n
Schritt 4) Für jedes Array-Element:
-
1.Bucket-Index berechnen:
bucket_index = (element - minimum)/span-
2.Fügen Sie das Element in den Bucket[bucket_index] ein.
Schritt 5) Sortieren Sie jeden Bucket mithilfe der Einfügungssortierung.
Schritt 6) Verketten Sie alle Buckets in einem einzigen Array.
Sehen wir uns ein Beispiel für diesen Bucket-Sort-Algorithmus an. Für dieses Beispiel sortieren wir das folgende Array mit dem Bucket-Sort-Algorithmus:
Schritt 1) Im ersten Schritt müssen die maximalen und minimalen Elemente des angegebenen Arrays ermittelt werden. In diesem Beispiel beträgt der Höchstwert 24 und der Mindestwert 1.
Schritt 2) Jetzt müssen wir eine Anzahl leerer Eimer auswählen, n. In diesem Beispiel nehmen wir 5 Eimer. Dann werden wir sie als leer initialisieren.
Schritt 3) Die Spannweite jedes Eimers muss mit der folgenden Formel berechnet werden:
span = (maximum-minimum)/n = (24-1)/5 = 4;
Daher enthält der erste Bucket die Zahlen im Bereich [0, 5). Der zweite Bucket enthält die Zahlen zwischen [5, 10) und so weiter.
Schritt 4) Für jedes Array-Element berechnen wir den Bucket-Index und platzieren das Element in diesem Bucket. Der Bucket-Index kann mit der Formel berechnet werden:
bucket_index = (element - minimum)/span
Berechnung des Bucket-Index:
-
a) 11bucket_index = (Element – Minimum)/Span
=(11-1)/4
=2
Daher wird Element 11 in Bucket[2] gespeichert.
-
b) 9
Bucket_index = (Element – Minimum)/Span
=(9-1)/4
=2
Hinweis: Da 9 ein Grenzelement für Bucket[1] ist, muss es in Bucket[1] angehängt werden, anstatt in denselben Bucket wie das vorherige Element.
Nachdem Sie die Operationen für jedes Element ausgeführt haben, sehen die Buckets wie folgt aus:
Schritt 5) Jetzt wird jeder Bucket mithilfe der Einfügungssortierung sortiert. Die Eimer nach dem Sortieren
Schritt 6) Im letzten Schritt werden die Buckets zu einem einzigen Array verkettet. Das Array wird das sortierte Ergebnis der Eingabe sein.
Bucket-Sort-Programm in C/C++
Eingang:
#include<bits/stdc++.h>
using namespace std;
void bucketSort(vector < double > & input, int No_Of_Buckets)
{
double max_value = * max_element(input.begin(), input.end());
double min_value = * min_element(input.begin(), input.end());
double span = (max_value - min_value) / No_Of_Buckets;
vector<vector <double>>
output;
for (int i = 0; i < No_Of_Buckets; i++)
output.push_back(vector <double>
());
for (int i = 0; i < input.size(); i++)
{
double difference = (input[i] - min_value) / span
-
int((input[i] - min_value) / span);
if (difference == 0 && input[i] != min_value)
output[int((input[i] - min_value) / span) - 1]
.push_back(input[i]);
else
output[int((input[i] - min_value) / span)].push_back(
input[i]);
}
for (int i = 0; i < output.size(); i++)
{
if (!output[i].empty())
sort(output[i].begin(), output[i].end());
}
int index = 0;
for (vector <double> & bucket: output)
{
if (!bucket.empty())
{
for (double i: bucket)
{
input[index] = i;
index++;
}
}
}
}
int main()
{
vector <double>
input ={11,9,21,8,17,19,13,1,24,12
};
int No_Of_Buckets = 5;
bucketSort(input, No_Of_Buckets);
cout<<
"Sorted Output:";
for (int i; i < input.size(); i++)
cout <<input[i]<<" ";
return 0;
}
Ausgang:
Sorted Output:1 8 9 11 12 13 17 19 21 24
Bucket-Sort-Programm in Python
Eingang:
def bucketSort(input, No_Of_Buckets):
max_element = max(input)
min_element = min(input)
span = (max_element - min_element) / No_Of_Buckets
output = []
for bucket in range(No_Of_Buckets):
output.append([])
for element in range(len(input)):
diff = (input[element] - min_element) / span - int(
(input[element] - min_element) / span
)
if diff == 0 and input[element] != min_element:
output[int((input[element] - min_element) / span) - 1].append(
input[element]
)
else:
output[int((input[element] - min_element) / span)].append(input[element])
for bucket in range(len(output)):
if len(output[bucket]) != 0:
output[bucket].sort()
index = 0
for bucket in output:
if bucket:
for element in bucket:
input[index] = element
index = index + 1
input = [11, 9, 21, 8, 17, 19, 13, 1, 24, 12]
No_Of_Buckets = 5
bucketSort(input, No_Of_Buckets)
print("Sorted Output:\n", input)
Ausgang:
Sorted Output: [1, 8, 9, 11, 12, 13, 17, 19, 21, 24]
Bucket-Sortierung in Java
Eingang:
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
public static void bucketSort(List < Double > input, int No_Of_Buckets) {
double max_value = Collections.max(input);
double min_value = Collections.min(input);
double span =(max_value - min_value) / No_Of_Buckets;
List <
List <
Double > >
output = new ArrayList < >
();
for (int i = 0; i < No_Of_Buckets; i++) {
output.add(new ArrayList < >
());
}
for (Double value: input) {
double difference = (value - min_value) / span - ((value - min_value) / span);
if (difference == 0 && value != min_value) {
output.get((int)((value - min_value) / span) - 1).add(value);
} else {
output.get((int)((value - min_value) / span)).add(value);
}
}
for (List <Double> bucket: output) {
if (!bucket.isEmpty()) {
Collections.sort(bucket);
}
}
int index = 0;
for (List <Double> bucket: output) {
if (!bucket.isEmpty()) {
for (Double value: bucket) {
input.set(index,value);
index++;
}
}
}
}
public static void main(String[] args) {
List <Double>
input = new ArrayList <>
();
input.add(11.0);
input.add(9.0);
input.add(21.0);
input.add(8.0);
input.add(17.0);
input.add(19.0);
input.add(13.0);
input.add(1.0);
input.add(24.0);
input.add(12.0);
int No_Of_Buckets = 5;
bucketSort(input, No_Of_Buckets);
System.out.println("Sorted Output:");
for (Double value: input) {
System.out.print(value + " ");
}
}
}
Ausgang:
Sorted Output: 1.0 8.0 9.0 11.0 12.0 13.0 17.0 19.0 21.0 24.0
Pros & Cons
| Vorteile | Nachteile |
|---|---|
| Führen Sie schnellere Berechnungen durch | Verbraucht mehr Platz im Vergleich zu anderen Algorithmen |
| Es kann als externe Sortiermethode verwendet werden | Die Leistung ist schlecht, wenn die Daten nicht gleichmäßig verteilt sind |
| Eimer können unabhängig voneinander verarbeitet werden |
Bucket-Sort-Komplexitätsanalyse
Zeitliche Komplexität von Bucket Sort
- beste Fallkomplexität:Wenn alle Array-Elemente vorher gleichmäßig verteilt und sortiert werden, würde es O(n) Zeit erfordern, die Elemente in die entsprechenden Buckets zu verteilen. Dann sortieren Sie jeden Eimer nach Sortieren durch Einfügen würde O(k) kosten. Somit wäre die Gesamtkomplexität O(n+k).
- Durchschnittliche Fallkomplexität:Im Durchschnitt gehen wir davon aus, dass die Eingaben gleichmäßig verteilt sind. Somit erreicht der Bucket-Sorting-Algorithmus eine lineare Zeitkomplexität von O(n+k). Dabei wird O(n) Zeit zum Streuen der Elemente und O(k) Zeit zum Sortieren dieser Elemente mittels Insertionsort benötigt.
- Komplexität im schlimmsten Fall:Im schlimmsten Fall werden die Elemente nicht gleichmäßig auf ein oder zwei bestimmte Eimer verteilt und konzentriert. In diesem Fall funktioniert die Bucket-Sortierung als Blasensortierungsalgorithmus. Daher wäre die Zeitkomplexität einer Bucketsortierung im schlimmsten Fall O(n^2).
Platzkomplexität der Bucket-Sortierung
Die Speicherkomplexität von Bucketsort beträgt O(n*k). Dabei ist n die Anzahl der Elemente und k die Anzahl der erforderlichen Buckets.
