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 mal lokal nach Straße, Hausnummer usw. sortiert und verteilt. 

Bucketsort Bucketsort

Erstelle Lernmaterialien über Bucketsort mit unserer kostenlosen Lern-App!

  • Sofortiger Zugriff auf Millionen von Lernmaterialien
  • Karteikarten, Notizen, Übungsprüfungen und mehr
  • Alles, was du brauchst, um bei deinen Prüfungen zu glänzen
Kostenlos anmelden
Inhaltsverzeichnis
Inhaltsangabe

    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

    Wie funktioniert 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. 

    Ist Bucketsort stabil? 

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

    Was ist Bucketsort? 

    Bucketsort ist ein stabiler, nicht vergleichsbasierter Sortieralgorithmus. 

    Wofür wird Bucketsort benutzt? 

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

    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
    1
    Über StudySmarter

    StudySmarter ist ein weltweit anerkanntes Bildungstechnologie-Unternehmen, das eine ganzheitliche Lernplattform für Schüler und Studenten aller Altersstufen und Bildungsniveaus bietet. Unsere Plattform unterstützt das Lernen in einer breiten Palette von Fächern, einschließlich MINT, Sozialwissenschaften und Sprachen, und hilft den Schülern auch, weltweit verschiedene Tests und Prüfungen wie GCSE, A Level, SAT, ACT, Abitur und mehr erfolgreich zu meistern. Wir bieten eine umfangreiche Bibliothek von Lernmaterialien, einschließlich interaktiver Karteikarten, umfassender Lehrbuchlösungen und detaillierter Erklärungen. Die fortschrittliche Technologie und Werkzeuge, die wir zur Verfügung stellen, helfen Schülern, ihre eigenen Lernmaterialien zu erstellen. Die Inhalte von StudySmarter sind nicht nur von Experten geprüft, sondern werden auch regelmäßig aktualisiert, um Genauigkeit und Relevanz zu gewährleisten.

    Erfahre mehr
    StudySmarter Redaktionsteam

    Team Bucketsort Lehrer

    • 9 Minuten Lesezeit
    • Geprüft vom StudySmarter Redaktionsteam
    Erklärung speichern

    Lerne jederzeit. Lerne überall. Auf allen Geräten.

    Kostenfrei loslegen

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

    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!