Bucket-Sort-Algorithmus (Java, Python, C/C++ Code Beispiele)

Was ist Bucket Sort?

Bucket Sort, oft auch Bin Sort genannt, ist ein vergleichsbasiertes Sortierverfahren, das ein unsortiertes Array als Eingabe erhält und ein sortiertes Array als Ausgabe erzeugt. Dabei werden die Elemente in mehrere Behälter (Buckets) aufgeteilt und jeder Behälter einzeln mithilfe eines anderen Sortieralgorithmus, wie beispielsweise Insertion Sort, sortiert. Anschließend werden alle Behälter zusammengeführt, um das endgültige sortierte Array zu bilden.

Bucket Sort wird häufig verwendet, wenn die Elemente folgende sind:

1. Gleitkommawerte
2. Gleichmäßig verteilt über einen bekannten Bereich

Die Zeitkomplexität des Bucket-Sort-Algorithmus hängt von der Anzahl der verwendeten Buckets und der Gleichmäßigkeit der Eingabeverteilung ab. Andere Sortieralgorithmen wie beispielsweise … Muschelsortierung, Zusammenführungssortierung, Heapsortierung und schnelle Sorte Wenn der Bucket-Sort-Algorithmus eine optimale Zeitkomplexität von O(n*logn) erreicht, kann er unter günstigen Bedingungen eine lineare Zeitkomplexität von O(n) erreichen.

Bucket Sort folgt dem Scatter-Gather-Prinzip. Die Elemente werden in entsprechende Buckets verteilt, innerhalb jedes Buckets sortiert und schließlich zu einem sortierten Array zusammengeführt. Dieses Scatter-Gather-Prinzip wird im folgenden Abschnitt erläutert.

Scatter-Gather-Ansatz

Umfangreiche, komplexe Probleme lassen sich mitunter nur schwer direkt lösen. Der Scatter-Gather-Ansatz begegnet solchen Problemen, indem er den gesamten Datensatz in Cluster unterteilt. Jeder Cluster wird separat verarbeitet, und die Ergebnisse werden anschließend zusammengeführt, um das Endergebnis zu ermitteln.

So implementiert der Bucket-Sort-Algorithmus die Scatter-Gather-Methode:

So funktioniert Bucket Sort

Das grundlegende Funktionsprinzip von Bucket Sort ist wie folgt:

1. Es wird eine Menge leerer Buckets erstellt. Je nach gewählter Richtlinie kann die Anzahl der Buckets variieren.
2. Aus dem Eingabe-Array wird jedes Element in den entsprechenden Bucket eingefügt.
3. Jeder Behälter wird einzeln mithilfe eines sekundären Sortieralgorithmus sortiert.
4. Die sortierten Buckets werden verkettet, um ein einzelnes Ausgabearray zu erzeugen.

Spitzname Code

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-Sort-Algorithmus für Gleitkommazahlen im Bereich [0.0, 1.0]:

Schritt 1) Erstelle zehn (10) leere Behälter. Der erste Behälter enthält Zahlen im Bereich [0.0; 0.1). Der zweite Behälter enthält Zahlen im Bereich [0.1; 0.2) usw.

Schritt 2) Für jedes Array-Element:

• a. Berechnen Sie den Bucket-Index mithilfe der folgenden Formel:
  bucket_index = Anzahl_der_buckets * array_element
• b. Füge das Element in bucket[bucket_index] ein.

Schritt 3) Sortieren Sie jeden Eimer einzeln mithilfe der Einfügungssortierung.

Schritt 4) Verknüpfe alle Buckets zu einem einzigen sortierten Array.

Betrachten wir ein Beispiel für Bucket Sort. In diesem Beispiel sortieren wir das folgende Array:

Schritt 1) Zuerst erstellen wir 10 leere Behälter. Der erste Behälter enthält Zahlen im Intervall [0.0, 0.1). Der zweite Behälter enthält Zahlen im Intervall [0.1, 0.2) usw.

Schritt 2) Berechne für jedes Array-Element den Bucket-Index und platziere das Element in diesem Bucket.

Der Bucket-Index wird anhand der folgenden Formel berechnet:
        bucket_index = Anzahl_der_buckets * array_element

Berechnung des Bucket-Index:
a) 0.78
      bucket_index = Anzahl_der_buckets * array_element
              = 10 · 0.78
              = 7.8
Daher wird das Element 0.78 in bucket[floor(7.8)] oder bucket[7] gespeichert.

b) 0.17
      bucket_index = Anzahl_der_buckets * array_element
              = 10 · 0.17
              = 1.7

Das Array-Element 0.17 wird in bucket[floor(1.7)] oder bucket[1] gespeichert.

c) 0.39
      bucket_index = Anzahl_der_buckets * array_element
              = 10 · 0.39
              = 3.9
0.39 wird in bucket[floor(3.9)] oder bucket[3] gespeichert.

Nach dem Durchlaufen aller Array-Elemente sehen die Buckets wie folgt aus:

Schritt 3) Jeder Bucket wird anschließend mittels Insertion Sort sortiert. Nach dem Sortiervorgang ergibt sich folgende Ausgabe:

Schritt 4) Im letzten Schritt werden die Buckets zu einem einzigen Array zusammengefügt. Dieses Array stellt das sortierte Ergebnis der Eingabe dar.

Jeder Bucket wird an das Ausgabearray angehängt. Zum Beispiel die Anhängung der Elemente des zweiten Buckets:

Die Verkettung der letzten Bucket-Elemente wird unten dargestellt:

Nach der Verkettung entsteht das gewünschte sortierte Array.

Bucket-Sort-Programm in C/C++

Eingang:

//Bucket Sort Program in C/C++
//For values without 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: 
";
  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 values without 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 Eingaben, die Zahlen außerhalb des Bereichs [0.0; 1.0] enthalten, unterscheidet sich geringfügig vom vorherigen. AlgorithmusDie für diesen Fall erforderlichen Schritte sind wie folgt:

Schritt 1) Finde das größte und das kleinste Element im Array.

Schritt 2) Wählen Sie die Anzahl der Buckets, n, und initialisieren Sie diese 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. Berechnen Sie den Bucket-Index:
          bucket_index = (element - minimum) / span
• 2. Füge das Element in bucket[bucket_index] ein.

Schritt 5) Sortieren Sie jeden Bucket mithilfe der Einfügungssortierung.

Schritt 6) Verketten Sie alle Buckets in einem einzigen Array.

Betrachten wir ein Beispiel für den Bucket-Sort-Algorithmus. In diesem Beispiel sortieren wir das folgende Array:

Schritt 1) Im ersten Schritt ermitteln wir das größte und das kleinste Element des gegebenen Arrays. In diesem Beispiel ist das größte Element 24 und das kleinste 1.

Schritt 2) Als Nächstes wählen wir die Anzahl der leeren Buckets, n. In diesem Beispiel verwenden wir 5 Buckets und initialisieren sie als leer.

Schritt 3) Die Spannweite jedes Eimers wird anhand der folgenden Formel berechnet:
        span = (maximum - minimum) / n = (24 - 1) / 5 = 4

Daher enthält der erste Behälter Zahlen im Bereich [0, 5). Der zweite Behälter enthält Zahlen im Bereich [5, 10) usw.

Schritt 4) Für jedes Array-Element wird der Bucket-Index berechnet und das Element in diesen Bucket eingefügt. Der Bucket-Index wird mit folgender Formel berechnet:
        bucket_index = (element - minimum) / span

Berechnung des Bucket-Index:

a) 11
Bucket-Index = (Element – ​​Minimum) / Spanne
        = (11-1) / 4
        = 2

Somit wird Element 11 in bucket[2] gespeichert.

b) 9
Bucket-Index = (Element – ​​Minimum) / Spanne
        = (9-1) / 4
        = 2

Hinweis: Da es sich bei 9 um ein Randelement für bucket[1] handelt, wird es an bucket[1] angehängt, anstatt im selben Bucket wie das vorherige Element platziert zu werden.

Nach Durchführung der Operationen für jedes Element sehen die Buckets wie folgt aus:

Schritt 5) Nun wird jeder Bucket mithilfe des Insertion Sort-Algorithmus sortiert. Die Buckets nach dem Sortieren:

Schritt 6) Im letzten Schritt werden die Buckets zu einem einzigen Array zusammengefügt. Array ist das sortierte Ergebnis der Eingabe.

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=0; 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:
", 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

Vor- und Nachteile der Bucket-Sortierung

Bucket-Sort-Komplexitätsanalyse

Bucket-Sortierung – Zeitkomplexität

• beste Fallkomplexität: Wenn alle Array-Elemente gleichmäßig verteilt und innerhalb jedes Buckets vorsortiert sind, benötigt das Aufteilen der Elemente in die entsprechenden Buckets O(n) Zeit. Anschließend wird jeder Bucket sortiert. Sortieren durch Einfügen Die Kosten betragen O(k). Die Gesamtkomplexität beträgt somit O(n+k).
• Durchschnittliche Fallkomplexität: Im Normalfall gehen wir von einer Gleichverteilung der Eingaben aus. Daher erreicht der Bucket-Sort-Algorithmus eine lineare Zeitkomplexität von O(n+k). Hierbei benötigt das Verteilen der Elemente O(n) Zeit und das Sortieren mittels Insertion Sort O(k) Zeit.
• Komplexität im schlimmsten Fall: Im schlimmsten Fall sind die Elemente nicht gleichmäßig verteilt und konzentrieren sich in einem oder zwei Buckets. In diesem Fall verhält sich Bucket Sort ähnlich wie ein … Bubble-Sort-AlgorithmusDaher beträgt die Zeitkomplexität von Bucket Sort im schlimmsten Fall O(n²).

Platzkomplexität der Bucket-Sortierung

Die Speicherkomplexität des Bucket-Sort-Algorithmus beträgt O(n*k). Hierbei ist n die Anzahl der Elemente und k die Anzahl der benötigten Buckets, um diese während des Sortiervorgangs aufzunehmen.

Häufig gestellte Fragen