Open in App
Login Anmelden

Select your language

Suggested languages for you:
StudySmarter - Die all-in-one Lernapp.
4.8 • +11k Ratings
Mehr als 5 Millionen Downloads
Free
|
|
Bucketsort

Wusstest Du, dass Briefe in Deutschland im Grunde nach einem Sortierverfahren sortiert werden? Die Briefe aus den Briefkästen werden gesammelt und in Briefzentren gebracht. Dort werden sie zunächst nach den ersten zwei Zahlen ihrer Postleitzahl sortiert – damit ist das Briefzentrum des Zielortes gekennzeichnet. Dort werden die Briefe dann noch…

Inhalt von Fachexperten überprüft
Kostenlose StudySmarter App mit über 20 Millionen Studierenden
Mockup Schule

Entdecke über 50 Millionen kostenlose Lernmaterialien in unserer App.

Illustration

Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken

Jetzt kostenlos anmelden

Nie wieder prokastinieren mit unseren Lernerinnerungen.

Jetzt kostenlos anmelden
Illustration

Wusstest Du, dass Briefe in Deutschland im Grunde nach einem Sortierverfahren sortiert werden? Die Briefe aus den Briefkästen werden gesammelt und in Briefzentren gebracht. Dort werden sie zunächst nach den ersten zwei Zahlen ihrer Postleitzahl sortiert – damit ist das Briefzentrum des Zielortes gekennzeichnet. Dort werden die Briefe dann noch mal lokal nach Straße, Hausnummer usw. sortiert und verteilt.

Das Konzept, das bei den Sortieralgorithmen dahintersteckt, ist Bucketsort. Was es damit genau auf sich hat, erfährst Du hier.

Sortieralgorithmen Bucketsort

Das Grundprinzip hinter dem Bucketsort Sortieralgorithmus ist es, Datenmengen in sogenannte Buckets ("Eimer") zu verteilen. Diese Eimer werden dann mit einem anderen Sortieralgorithmus sortiert und anschließend wieder zu einer Liste zusammengeführt.

Bucketsort Definition

Bucketsort ist ein nicht vergleichsbasierter Sortieralgorithmus, der out-of-place Datenmengen mithilfe von Buckets und einem anderen selbst gewählten Sortierverfahren sortiert.

Wie der Bucketsort Algorithmus genau vorgeht, erfährst Du im folgenden Abschnitt.

Bucketsort Algorithmus

Am einfachsten lässt sich Bucketsort durch ein Beispiel erklären. Gegeben ist folgendes Array:

0.520.220.830.410.940.780.250.310.160.72

Schritt 1

Zunächst werden zehn verschiedene Buckets mit Indexen von 0 bis 9 angelegt. Die "Beschriftung" der Buckets ist dabei nicht vorgegeben, sprich, Du kannst die Buckets anwendungsbezogen benennen. Es wäre auch denkbar Ober- und Untergrenzen für einen Bucket zu definieren, anstatt einer konkreten Zahl.

Bucket0123456789

Danach sortierst Du das gegebene Array in die einzelnen Buckets ein. Sortiert wird erst mal nur nach der ersten Nachkommazahl.

Wichtig ist dabei, dass Du die Elemente immer von oben in die Buckets packst, damit die Reihenfolge an dieser Stelle noch nicht vertauscht wird!

0.250.72
0.160.220.310.410.520.780.830.94
Bucket0123456789

Schritt 2

Im zweiten Schritt wendest Du dann einen anderen Sortieralgorithmus an, um die Elemente innerhalb der einzelnen Buckets zu sortieren. In diesem Fall wird dafür Insertion Sort verwendet.

Mehr zur Vorgehensweise von Insertion Sort findest Du in der gleichnamigen Erklärung auf StudySmarter.

Beim gegebenen Beispiel musst Du lediglich die Buckets 2 und 7 genauer betrachten, da diese mehr als ein Element enthalten. Die Elemente in Bucket 2 sind bereits in der richtigen Reihenfolge, die Elemente in Bucket 7 müssen jedoch noch vertauscht werden.

0.250.78
0.160.220.310.410.520.720.830.94
Bucket0123456789

Schritt 3

Der letzte Schritt ist dann, die einzelnen Buckets wieder zusammenzuführen – das wird auch Konkatenation genannt. Als Endergebnis erhältst Du ein vollständig sortiertes Array:

0.160.220.250.310.410.520.720.780.830.94

Unter einer Konkatenation versteht man das Zusammenfügen von zwei Listen zu einer Liste. Dabei wird die Reihenfolge der Elemente nicht verändert.

Bucketsort Vorgehensweise

Noch mal kurz und knapp, wie wird Bucketsort durchgeführt:

  • Initialisiere Buckets und sortiere die gegebene Datenmenge hinein

  • Wähle einen Sortieralgorithmus (z. B., Insertion Sort) und sortiere damit die einzelnen Buckets, falls notwendig

  • Konkateniere die Buckets zu einem fertig sortierten Array

Ein Beispiel zum Sortieren von Fließkommazahlen mit Bucketsort in Java findest Du weiter unten in den Beispielen.

Bucketsort Komplexität

Bei der Komplexität müssen die Laufzeit (Zeitkomplexität) und der zusätzliche Speicherbedarf (Platzkomplexität) unterschieden werden.

Beachte, dass die Laufzeit bei Bucketsort auch abhängig vom verwendeten Sortieralgorithmus für die einzelnen Buckets ist! Mehr zu möglichen Sortierverfahren findest Du in eigenständigen Erklärungen auf StudySmarter oder als Überblick zusammengefasst in der Erklärung zu den Sortieralgorithmen.

Bucketsort Laufzeit

Die Laufzeit beim Bucketsort Sortieralgorithmus muss in Best-Case, Average-Case und Worst-Case unterschieden werden.

Best-Case

Der Best-Case geht davon aus, dass Datenmengen möglichst gleichmäßig in den einzelnen Buckets verteilt sind. Je nach verwendetem Sortieralgorithmus für das Sortieren in den Buckets, kann sogar eine lineare Komplexität erreicht werden (z. B. mit Insertion Sort). In diesem Fall würde die Laufzeit O(n + k) betragen.

O(n) steht für das Erstellen der Buckets und O(k) für das Sortieren der Daten mit einem Sortieralgorithmus, der im besten Fall eine lineare Zeitkomplexität hat.

Average-Case

Ist eine Datenmenge zufällig verteilt, liegt der Average-Case vor. Bucketsort läuft dabei ebenfalls in linearer Zeit ab – hat also eine Zeitkomplexität von O(n).

Worst-Case

Landen viele Elemente in den gleichen Buckets, hängt die Komplexität stark von dem Sortierverfahren ab, das die einzelnen Buckets sortiert. Befinden sich die Daten dann noch in der falschen Reihenfolge, verschlechtert sich die Laufzeit noch weiter.

Wird Insertion Sort zum Sortieren der Buckets verwendet, liegt die Zeitkomplexität bei O(n2), normalerweise wird aber auch hier von einer Laufzeit von O(n + k) ausgegangen.

Bucketsort Speicherbedarf

Bucketsort hat einen größeren Speicherbedarf als z. B. Insertion Sort oder Selection Sort. Außerdem arbeitet der Algorithmus out-of-place. Die Platzkomplexität ist dabei ebenfalls linear und beträgt O(n + k).

Bucketsort – Weitere Begrifflichkeiten

Weitere Begrifflichkeiten, die rund um Bucketsort erläutert werden sollen, sind:

  • Stabilität

  • Vergleichsbasiert

  • Parallelisierbarkeit

Bucketsort stabil – instabil

Ob Bucketsort stabil ist, hängt vom verwendeten Verfahren innerhalb der Buckets ab. Wenn Du dort ein stabiles Sortierverfahren wie Bubble Sort oder Insertion Sort benutzt, ist auch Bucketsort stabil.

Bucketsort vergleichsbasiert

Bucketsort gehört zu den nicht vergleichsbasierten Sortieralgorithmen. Das heißt, es werden keine zwei Elemente direkt miteinander verglichen, um Datenmengen zu sortieren. Stattdessen werden die Daten vorsortiert und dann in ihren jeweiligen Buckets weiter sortiert.

Bucketsort Parallelisierbarkeit

Eine Parallelisierung ist beim Bucketsort Sortierverfahren ebenfalls umsetzbar. Am einfachsten kannst Du die Parallelisierbarkeit erreichen, indem Du jedem Bucket einen eigenen Prozessor zuweist.

Allerdings muss dann jeder Prozessor das gegebene Array überprüfen, um die entsprechenden Daten für sein Bucket zu finden und das kostet unnötige Rechenzeit.

Eine bessere Lösung wäre es, die Datenmengen vorher in einzelne Teilbereiche zu zerlegen und diese dann jeweils einem Prozessor zuzuweisen. Die Prozessoren würden dann ihre Liste in kleine Buckets einteilen und diese anschließend zur Einsortierung in die eigentlichen Buckets weiterschicken. Von dort aus werden die Daten dann endgültig sortiert und wieder zu einem Array zusammengefügt.

Bucketsort Zusammenfassung

In der folgenden Übersicht findest Du das bisher Gelernte auf einem Blick:

Best-CaseAverage-CaseWorst-CasePlatz-komplexitätStabiles Verfahrenvergleichs-basiertIn-PlaceParallelisier-barkeit
O(n + k)O(n)O(n + k)O(n + k)JaNeinNeinMöglich

Bucketsort Vorteile

Das Bucketsort Sortierverfahren bringt verschiedene Vorteile:

Bucketsort Vorteile
Schnelles Sortierverfahren, das keine Vergleiche benötigt.
Gut geeignet für große Datenmengen, wenn es sich um natürliche Zahlen handelt.
Übersichtliche Code-Implementation möglich.

Bedenke dabei, dass die Vorteile – und auch die Nachteile – vom zweiten verwendeten Sortieralgorithmus sowohl positiv als auch negativ beeinflusst werden können.

Verwendest Du z. B. einen einfachen Sortieralgorithmus wie Insertion Sort oder Selection Sort zum Sortieren der einzelnen Buckets kann das die Zeitkomplexität auf O(n2) verschlechtern. Ähnliches gilt, wenn Du als zweiten Algorithmus ein instabiles Sortierverfahren wählst – denn dann wird auch Bucketsort instabil.

Bucketsort Nachteile

Neben Vorteilen hat Bucketsort auch Nachteile:

Bucketsort Nachteile
Hoher Speicherplatzbedarf notwendig – je nachdem, wie viele Daten sortiert werden sollen und wie viele Buckets benötigt werden.
Der Algorithmus ist auf wenige Schlüsselwerte beschränkt.

Den letzten Nachteil kannst Du durch eine Weiterentwicklung vom Bucketsort, dem Radixsort lösen. Mehr zum Radix Sort findest Du in einer eigenen Erklärung auf StudySmarter.

Bucketsort Beispiel

Nun folgen ein paar weitere (Code-)Beispiele zum Bucketsort.

Bucketsort Anwendung

Zunächst wird noch die Frage geklärt, wann Bucketsort angewendet wird:

  • zum alphabetischen Sortieren von Wörtern
  • bei Fließkommazahlen
  • wenn Eingabedaten gleichmäßig über einen Bereich verteilt sind

Bucketsort Code

Wie könnte Bucketsort Code aussehen? Zunächst folgt etwas Pseudocode:

Bucketsort (liste, funktion)

  n = liste.size
  bucket = intervall(n)

// Elemente in Buckets vorsortieren
    for (element in liste)
      bucket[floor (funktion(element) * n].add(element)
  array []

// hier werden die Elemente in den Buckets mithilfe von Insertionsort sortiert
  for (daten in buckets)
    x.insertionsort(daten)
    array.append(x)

  return array

Jetzt folgt noch ein Beispiel, wie eine Implementation von Bucketsort in Java-Code aussehen könnte:

import Java.util.ArrayList;
import Java.util.Collections;

public class BucketSort {

  public void bucketSort(float[] arr, int n) {
    if (n <= 0)
      return;
    ArrayList[] bucket = new ArrayList[n];

    // Erzeuge leere Buckets
      for (int i = 0; i < n; i++)
      bucket[i] = new ArrayList();

    // Einfügen von Elementen in die Buckets 
    for (int i = 0; i < n; i++) {
      int bucketIndex = (int) arr[i] * n;
      bucket[bucketIndex].add(arr[i]);
    }

    // Sortieren der Elemente in jedem Bucket
    for (int i = 0; i < n; i++) {
      Collections.sort((bucket[i]));
    }

    // Sortiertes Array erzeugen 
    int index = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0, size = bucket[i].size(); j < size; j++) {
        arr[index++] = bucket[i].get(j);
      }
    }
  }

  // Treibercode
  public static void main(String[] args) {
    BucketSort b = new BucketSort();
    // Anlegen eines neuen Arrays mit unsortierten Daten
    float[] arr = { (float) 0.52, (float) 0.22, (float) 0.83, (float) 0.41, (float) 0.94, (float) 0.78,
        (float) 0.25, (float) 0.31, (float) 0.16, (float) 0.72 };
    // Funktion Buckesort aufrufen | arr = vorher definiertes Array mit Fließkommazahlen | n =7 
    b.bucketSort(arr, 10);
    // Sortiertes Array ausgeben lassen
    for (float i : arr)
      System.out.print(i + "  ");
  }
}

Ausgabe:

0.16 0.22 0.25 0.31 0.41 0.52 0.72 0.78 0.83 0.94


Bucketsort – Das Wichtigste

  • Unter Sortieralgorithmen Bucketsort versteht man einen nicht vergleichsbasierten, stabilen Sortieralgorithmus, der out-of-place Datenmengen mithilfe von Buckets und einem anderen Sortierverfahren sortiert.
  • Bucketsort hat eine lineare Zeitkomplexität von O(n + k) und einen zusätzlichen Speicherbedarf von O(n + k).
  • Bucketsort Vorteile: Schnelles Sortierverfahren; benötigt keine Vergleiche; gut geeignet für große Datenmengen.

  • Bucketsort Nachteile: Hoher zusätzlicher Speicher nötig; auf wenige Schlüsselwerte beschränkt. Der letzte Punkt kann durch eine Weiterentwicklung vom Bucketsort, dem Radixsort, gelöst werden.

  • Bucketsort Anwendung:

    • zum alphabetischen Sortieren von Wörtern
    • bei Fließkommazahlen
    • wenn Eingabedaten gleichmäßig über einen Bereich verteilt sind

Nachweise

  1. Marcel Klinger (2021). Bucketsort. Klinger.nrw (09.11.2022)
  2. Programiz.com: Bucket Sort Algorithm. (09.11.2022)
  3. Dr. Thomas Hinze (2016). Einführung in die Programmierung. Users.fmi.uni-jena.de (10.11.2022)

Häufig gestellte Fragen zum Thema Bucketsort

Bucketsort sortiert Datenmengen in Buckets vor. Diese werden dann mit einem anderen Sortieralgorithmus sortiert und anschließend wieder zu einer gemeinsamen Liste zusammengeführt. 

Solange der verwendete Sortieralgorithmus zum Sortieren der einzelnen Buckets stabil ist, ist auch Bucketsort stabil.  

Bucketsort ist ein stabiler, nicht vergleichsbasierter Sortieralgorithmus. 

Bucketsort wird z. B. zum Sortieren von Fließkommazahlen oder zum alphabetischen Sortieren verwendet. 

Finales Bucketsort Quiz

Bucketsort Quiz - Teste dein Wissen

Frage

Ergänze

Bucketsort ist ein ____ _____ (1) Sortieralgorithmus, der out-of-place Datenmengen mithilfe von ______ (2) und einem anderen selbst gewählten ______ (3) sortiert. 

Antwort anzeigen

Antwort

(1) nicht vergleichsbasierter

(2) Buckets  

(3) Sortierverfahren  

Frage anzeigen

Frage

Erkläre das Grundprinzip des Bucketsort.

Antwort anzeigen

Antwort

Das Grundprinzip hinter dem Bucketsort Sortieralgorithmus ist es, Datenmengen in sogenannte Buckets ("Eimer") zu verteilen. Diese Eimer werden dann mit einem anderen Sortieralgorithmus sortiert und anschließend wieder zu einer Liste zusammengeführt. 

Frage anzeigen

Frage

Wahr oder falsch

Elemente werden immer von oben in die Buckets einsortiert.

Antwort anzeigen

Antwort

Wahr

Frage anzeigen

Frage

Wie nennt man das Zusammenführen der einzelnen Buckets?

Antwort anzeigen

Antwort

Konkatenation

Frage anzeigen

Frage

Ergänze

Unter einer ______ (1) versteht man das Zusammenfügen von zwei Listen zu einer Liste. Dabei wird die ______ (2) der Elemente nicht verändert. 

Antwort anzeigen

Antwort

(1) Konkatenation 

(2) Reihenfolge 

Frage anzeigen

Frage

Bringe die folgende Vorgehensweise in die richtige Reihenfolge: 

(1) Wähle einen Sortieralgorithmus und sortiere damit die einzelnen Buckets

(2) Konkateniere die Buckets zu einem Array

(3) Initialisiere Buckets und sortiere die gegebene Datenmenge hinein

Antwort anzeigen

Antwort

3, 1, 2

Frage anzeigen

Frage

Welche Laufzeit hat Bucketsort?

Antwort anzeigen

Antwort

O(n + k)

Frage anzeigen

Frage

Wie lautet die Platzkomplexität von Bucketsort?

Antwort anzeigen

Antwort

O(n + k)

Frage anzeigen

Frage

Wann liegt bei Bucketsort der Best-Case vor?

Antwort anzeigen

Antwort

Der Best-Case liegt vor, wenn eine Datenmenge möglichst gleichmäßig in einzelne Buckets verteilt werden kann.

Frage anzeigen

Frage

Wahr oder falsch

Bucketsort ist ein instabiler Sortieralgorithmus.

Antwort anzeigen

Antwort

Falsch

Frage anzeigen

Frage

Wahr oder falsch

Bucketsort arbeitet nicht vergleichsbasiert. Stattdessen werden Daten vorsortiert und dann in ihren jeweiligen Buckets weiter sortiert. 

Antwort anzeigen

Antwort

Wahr

Frage anzeigen

Frage

Wahr oder falsch

Bucketsort ist parallelisierbar.

Antwort anzeigen

Antwort

Wahr

Frage anzeigen

Frage

Ergänze

Bucketsort arbeitet ______ .

Antwort anzeigen

Antwort

out-of-place

Frage anzeigen

Frage

Nenne drei Vorteile von Bucketsort.

Antwort anzeigen

Antwort

  • Schnelles Sortierverfahren, das keine Vergleiche benötigt.
  • Gut geeignet für große Datenmengen, wenn es sich um natürliche Zahlen handelt.
  • Übersichtliche Code-Implementation möglich. 

Frage anzeigen

Frage

Nenne zwei Nachteile von Bucketsort.

Antwort anzeigen

Antwort

  • Hoher Speicherplatzbedarf notwendig.
  • Der Algorithmus ist auf wenige Schlüsselwerte beschränkt. 

Frage anzeigen

Teste dein Wissen mit Multiple-Choice-Karteikarten

Wahr oder falschElemente werden immer von oben in die Buckets einsortiert.

Welche Laufzeit hat Bucketsort?

Wann liegt bei Bucketsort der Best-Case vor?

Weiter

Karteikarten in Bucketsort15

Lerne jetzt

Ergänze

Bucketsort ist ein ____ _____ (1) Sortieralgorithmus, der out-of-place Datenmengen mithilfe von ______ (2) und einem anderen selbst gewählten ______ (3) sortiert. 

(1) nicht vergleichsbasierter

(2) Buckets  

(3) Sortierverfahren  

Erkläre das Grundprinzip des Bucketsort.

Das Grundprinzip hinter dem Bucketsort Sortieralgorithmus ist es, Datenmengen in sogenannte Buckets ("Eimer") zu verteilen. Diese Eimer werden dann mit einem anderen Sortieralgorithmus sortiert und anschließend wieder zu einer Liste zusammengeführt. 

Wahr oder falsch

Elemente werden immer von oben in die Buckets einsortiert.

Wahr

Wie nennt man das Zusammenführen der einzelnen Buckets?

Konkatenation

Ergänze

Unter einer ______ (1) versteht man das Zusammenfügen von zwei Listen zu einer Liste. Dabei wird die ______ (2) der Elemente nicht verändert. 

(1) Konkatenation 

(2) Reihenfolge 

Bringe die folgende Vorgehensweise in die richtige Reihenfolge: 

(1) Wähle einen Sortieralgorithmus und sortiere damit die einzelnen Buckets

(2) Konkateniere die Buckets zu einem Array

(3) Initialisiere Buckets und sortiere die gegebene Datenmenge hinein

3, 1, 2

Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

Die erste Lern-App, die wirklich alles bietet, was du brauchst, um deine Prüfungen an einem Ort zu meistern.

  • Karteikarten & Quizze
  • KI-Lernassistent
  • Lernplaner
  • Probeklausuren
  • Intelligente Notizen
Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App! Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

Finde passende Lernmaterialien für deine Fächer

Melde dich an für Notizen & Bearbeitung. 100% for free.

Fang an mit StudySmarter zu lernen, die einzige Lernapp, die du brauchst.

Jetzt kostenlos anmelden
Illustration