Eimer-Sortierung

1. Bucket-Sortieralgorithmus
2. Beispiel für Bucket-Sortierung
3. Implementierung des Bucket-Sortieralgorithmus
4. Bucket-Sortieralgorithmus Komplexität

Bucket Sort ist ein Sortieralgorithmus vom Typ Vergleich. Er sortiert Elemente, indem er sie in Buckets oder Bins verteilt und einen anderen Algorithmus (normalerweise Insertion Sort) verwendet, um den Inhalt der einzelnen Buckets zu sortieren. Die einzelnen sortierten Buckets werden dann aneinander angehängt, um das endgültige sortierte Array zu erhalten. Dieser Ansatz des Sortieralgorithmus ist auch als Scatter-Gather-Ansatz bekannt. Er wird hauptsächlich verwendet, wenn die Eingabe gleichmäßig über einen Bereich wie z. B. Fließkommazahlen im Bereich von 0.00 bis 1.00 verteilt ist.

Bucket-Sortieralgorithmus

Nehmen wir an, dass wir ein unsortiertes Array A[] mit n Elementen haben.

Beispiel für Bucket-Sortierung

Angenommen, wir haben das Array: (0.22,0.33,0.1,0.45,0.38,0.55,0.21,0.31). Wir werden es mit dem Bucket-Sortieralgorithmus sortieren.

• Bilden Sie 10 Buckets mit jeweils dem Bereich 0.1.

• Nach dem Einfügen der Elemente in die Buckets erhalten wir:

• Einzelne Buckets sortieren, um zu erhalten:

Wenn wir alle Ergebnisse aneinander hängen, erhalten wir das endgültige sortierte Array als: (0.1,0.21,0.22,0.31,0.33,0.38,0.45,0.55).

Implementierung des Bucket-Sortieralgorithmus

#include <bits/stdc++.h>
using namespace std;

void bucketSort(float *array, int size) {
  vector<float> bucket[size];
  // insert elements into different buckets.
  for (int i = 0; i < size; i++) {
    bucket[int(size * array[i])].push_back(array[i]);
  }
  // sort individual buckets.
  for (int i = 0; i < size; i++) {
    sort(bucket[i].begin(), bucket[i].end());
  }

  int index = 0;
  for (int i = 0; i < size; i++) {
    while (!bucket[i].empty()) {
      array[index++] = *(bucket[i].begin());
      bucket[i].erase(bucket[i].begin());
    }
  }
}

int main() {
  int n = 8;
  float arr[8] = {0.22, 0.33, 0.1, 0.45, 0.38, 0.55, 0.21, 0.31};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  bucketSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Bucket-Sortieralgorithmus Komplexität

Zeitkomplexität

• Durchschnittlicher Fall

Der durchschnittliche Fall tritt ein, wenn die Elemente zufällig verteilt sind, und der Algorithmus liefert sehr effiziente Ergebnisse. Die Zeitkomplexität liegt in der Größenordnung von [Big Theta]: O(n+k). Es ist einer der wenigen Algorithmen mit durchschnittlich linearer Zeitkomplexität, und diese Komplexität gilt, wenn die Summe der Quadrate der Bucket-Größen linear in n ist.

• Schlechtester Fall

Der ungünstigste Fall tritt ein, wenn viele Elemente im Array nahe beieinander liegen und im selben Bucket zusammengefasst werden. Dadurch werden alle Vorteile der Aufteilung der Eingaben in Buckets zunichte gemacht, und die Gesamtkomplexität wird vom verwendeten Sortieralgorithmus abhängig. Insertion Sort hat eine Worst-Case-Zeitkomplexität von O(n²), wenn die Elemente in umgekehrter Reihenfolge angeordnet sind. Die Worst-Case-Zeitkomplexität ist also [Big O] O(n²).

• Bester Fall

Der beste Fall tritt ein, wenn die Elemente gleichmäßig in allen Buckets verteilt sind, oder wir ein bereits sortiertes Array erhalten. Die gesamte Zeitkomplexität setzt sich aus der Zeit für die Erstellung der Buckets O(n) und der Zeit für die Sortierung O(k) zusammen. Die Zeitkomplexität im besten Fall ist [Big Omega]: O(n+k).

Raumkomplexität

Die Raumkomplexität im schlimmsten Fall für den Bucket-Sortieralgorithmus ist O(n*k), wobei n die Anzahl der Elemente und k die Anzahl der Buckets ist. Die Platzkomplexität kann auf O(n+k) reduziert werden, indem der Platz für die Aufnahme aller Elemente und die Speicherung von Zeigern auf den Anfang des Buckets reduziert wird.