5.6 Ein Bucketsort

Rekapitulation Distributionsort

Bereits in der Folge 2 hatten wir einen sehr einfachen Sortieralgorithmus besprochen, den Distributionsort. Die Grundidee dieses Verfahrens besteht darin, jedes Element gemäß seinem Wert in eine passende Schublade einzuordnen und anschließend die Schubladen in der richtigen Reihenfolge auszulesen. Beim Distributionsort hatten wir für jede Zahl, die in dem Array vorkommt, eine eigene Schublade erzeugt. Kommen in einem aus 1000 Elementen bestehendem Array 214 verschiedene Zahlen vor, benötigen wir für den Distributionsort genau 214 Schubladen bzw. einen Verteilungsarray mit 214 Elementen. Für jedes Vorkommen der Zahl i wird dann das Arrayelement verteilung[i] um 1 inkrementiert.

Der Bucketsort-Algorithmus

Auch das Verfahren, das wir jetzt besprechen, ist noch eine relativ einfache Variante des Bucketsorts. Aber immerhin ein gewaltiger Fortschritt gegenüber dem simplen Distributionsort.

Vor dem ersten Sortierschritt
Autor: Ulrich Helmich 11/2025, Lizenz: Public domain

Dieses Bild zeigt einen kleinen Array mit Zahlen im Bereich 6 bis 57. In der unteren Reihe sehen wir sechs Eimer, engl. Buckets, die Arrayelemente aufnehmen können. Der erste Eimer ist für die Zahlen 0 bis 9 zuständig, der zweite für die Zahlen 10 bis 19 und so weiter. Der letzte Eimer schließlich kann die Zahlen 50 bis 59 aufnehmen.

Verteilung der ersten sechs Zahlen des Arrays
Autor: Ulrich Helmich 11/2025, Lizenz: Public domain

Der Array wurde hier schon bis zum sechsten Element (Index 5) durchlaufen. Die Zahlen, die in den Arrayelementen stehen, wurden in den jeweils passenden Eimer einsortiert. Zur Zeit enthält jeder Eimer nur eine Zahl. Aber wir sind ja auch noch nicht fertig.

Verteilung aller Zahlen
Autor: Ulrich Helmich 11/2025, Lizenz: Public domain

Der Arraydurchlauf ist jetzt beendet, und alle im Array vorkommenden Zahlen wurden in die Eimer einsortiert - und zwar nicht aufsteigend oder absteigend, sondern in der Reihenfolge, wie sie im Array vorgekommen sind.

Sortieren der Zahlen in den Buckets
Autor: Ulrich Helmich 11/2025, Lizenz: Public domain

Jetzt werden die Zahlen in jedem Bucket sortiert. Dazu kann durchaus ein einfacher Sortieralgorithmus wie Bubblesort oder Insertionsort benutzt werden. Eine grundsätzliche Alternative wäre aber auch möglich, nämlich die Zahlen bereits beim Einfügen in die Buckets korrekt einzusortieren, ähnlich wie im Insertionsort.

Zurückkopieren der Zahlen in den Buckets
Autor: Ulrich Helmich 11/2025, Lizenz: Public domain

Jetzt werden die sortierten Zahlen aus den Buckets wieder in den eigentlichen Array kopiert. Auf dem Bild sieht man die Situation, nachdem der zweite Eimer "geleert" wurde.

Der Bucketsort ist abgeschlossen
Autor: Ulrich Helmich 11/2025, Lizenz: Public domain

Hier schließlich sehen wir die Situation, nachdem auch der letzte Eimer geleert wurde.

Der Quelltext

Konstanten

public class Eimer
{
    private final int MAX = 12;      // Anzahl Elemente im Hauptarray
    private final int MAXWERT = 57;  // Wertebereich: 1..MAXWERT

    private int[] zahlen;

Hier sehen wir den Kopf der Klasse Eimer. Die Anzahl der Arrayelemente wurde hier auf MAX = 12 festgelegt, und der höchste vorkommende Wert ist MAXWERT = 57. Damit bezieht sich der Quelltext direkt auf unser Beispiel mit den sechs Eimern. Der zu sortierende Array wurde als Instanzvariable zahlen[] festgelegt.

Konstruktor

Betrachten wir nun den Konstruktor der Klasse Eimer:

    public Eimer()
    {
        zahlen = ArrayTools.erzeugeArray(MAX);
        ArrayTools.fuelleArrayMitZufallszahlen(zahlen, MAX, 1, MAXWERT);

        System.out.println("Anzeigen des unsortierten Arrays");
        ArrayTools.zeigeArray(zahlen, MAX);

        bucketSortMitListe();
        

        System.out.println("\nAnzeigen des sortierten Arrays");
        ArrayTools.zeigeArray(zahlen, MAX);        
    }

Mit der Methode erzeugeArray() der Klasse ArrayTools wird nun ein int-Array mit 12 Zahlen deklariert und initialisiert. Die Zuweisung der Werte findet dann mithilfe der Methode

ArrayTools.fuelleArrayMitZufallszahlen(zahlen, MAX, 1, MAXWERT);

statt. Dieser Methode werden der zu füllende Array, die Anzahl der zu erzeugenden Elemente, der kleinste Wert und der größte Wert als Parameter übergeben.

Dann wird - zur Kontrolle - der erzeugte Array in der Konsole ausgegeben, mithilfe der Methode ArrayTools.zeigeArray().

Jetzt wird die eigentliche Bucketsort-Methode bucketSortMitListe() aufgerufen, und anschließend wird - wieder zur Kontrolle - der (hoffentlich) sortierte Array in der Konsole ausgegeben.

Die Methode bucketSortMitListe()

Kopf und Konstanten

Betrachten wir zunächst den Kopf der Methode und eine Konstante:

public void bucketSortMitListe()
{
    final int BUCKETS = (MAXWERT / 10) + 1;

Die Anzahl der Eimer wird hier aus dem höchsten Wert der Zahlen MAXWERT und der Eimerbreite B = 10 berechnet. Unter der Eimerbreite (bucket width) versteht man den Wertebereich, der innerhalb eines Eimers gespeichert werden soll. In unserem Beispiel waren das jeweils 10 Zahlen, zum Beispiel im ersten Eimer die Zahlen 0..9, im zweiten Eimer die Zahlen 10..19 und so weiter.

Anlegen der Buckets

    Liste[] bucket = new Liste[BUCKETS];
    for (int i = 0; i < BUCKETS; i++)
        bucket[i] = new Liste();

Diese drei Zeilen sind nicht ohne Erläuterung verständlich. Wir müssen uns zunächst die Klasse Liste näher anschauen.

Die Klasse Liste

public class Liste
{
    int[] element;
    int   anzahl;
    
    public Liste()
    {
        element = new int[100];
        anzahl  = 0;
    }
    
    public void fuegeEin(int neu)
    {
        if (anzahl >= 100)
            return;

        // 1. Einfügeposition ermitteln (erste Position, an der neu <= element[i] ist)
        int pos = 0;
        while (pos < anzahl && element[pos] < neu)
            pos++;

        // 2. Alle Elemente rechts von pos um eine Position nach rechts verschieben
        for (int i = anzahl; i > pos; i--)
            element[i] = element[i - 1];

        // 3. Neues Element einfügen
        element[pos] = neu;

        // 4. Anzahl erhöhen
        anzahl++;
    }
    
    public void zeigeAn()
    {
       ArrayTools.zeigeArray(element,anzahl);
    }
}

Diese Klasse stellt im Prinzip ein int-Array zur Verfügung, das beim Erzeugen noch keine Elemente besitzt (anzahl = 0). Entscheidend ist die Methode fuegeEin(int neu). Diese Methode hängt nämlich nicht nur einfach eine neue Zahl an das Array an, sondern sortiert die neue Zahl sofort korrekt in das Array ein. Die erste Schleife (while) ermittelt die Einfügeposition, die zweite Schleife (for) verschiebt alle Elemente rechts der Einfügeposition um eine Stelle weiter nach rechts. Dann erst kann das neue Element eingefügt werden. Als viertes wird dann die Instanzvariable anzahl inkrementiert.

Die zeigeAn()-Methode am Ende dient nur zu Kontrollzwecken.

Welchen Sinn hat die Klasse Liste?

Wenn Sie das Beispiel am Anfang dieser Seite aufmerksam studiert haben, wird Ihnen aufgefallen sein, dass die Zahlen des Arrays zunächst völlig ungeordnet in die Eimer "fallen". Wenn das ganze Array abgearbeitet wurde, müssen die Zahlen in den sechs Eimern sortiert werden.

Das kann mithilfe eines einfachen Sortieralgorithmus wie Insertionsort geschehen. Alternativ kann man aber auch dafür sorgen, dass die Zahlen sofort korrekt in die Eimer einsortiert werden. Genau diese Aufgabe übernimmt hier die Klasse Liste bzw. die Methode fuegeEin().

Kommen wir zurück zu unserem Ausgangspunkt, dem Anlegen der Buckets. Betrachten wir jetzt noch einmal die ersten Zeilen der Methode bucketSortMitListe().

Anlegen der Buckets, Fortsetzung

    Liste[] bucket = new Liste[BUCKETS];
    for (int i = 0; i < BUCKETS; i++)
        bucket[i] = new Liste();

Hier wird ein Objekt-Array mit Objekten der Klasse Liste angelegt. Jeder Eimer ist jetzt eine Liste. Das heißt, die Zahlen, die in die Eimer "fallen", werden sofort an Ort und Stelle korrekt einsortiert, jeder Eimer enthält dann ein sortiertes Array von Zahlen. Die Konstante BUCKETS repräsentiert die Anzahl der Eimer. In unserem Quelltext hatten wir diese Konstante auf den Wert 6 gesetzt. Also besitzt das Array bucket jetzt sechs Objekte der Klasse Liste.

Zahlen in die Buckets einfügen

    for (int i = 0; i < MAX; i++)
    {
        int z = zahlen[i];
        int b = z / 10;
        bucket[b].fuegeEin(z);  
    }

Die for-Schleife durchläuft das gesamte Zahlen-Array. Der jeweils gefundene Wert wird in der lokalen Variablen z gespeichert. Der Index b des passenden Buckets wird durch die Formel b = z / 10 berechnet.

Angenommen, die gefundene Zahl ist 38. Die Ganzahl-Division 38/10 liefert den Wert 3. Das heißt, die 38 wird in das bucket-Objekt mit dem Index 3 einsortiert, also in den vierten Eimer. Hier noch einmal das passende Bild aus unserem Beispiel.

Die Zahl 38 befindet sich im vierten Eimer mit dem Index 3
Autor: Ulrich Helmich 11/2025, Lizenz: Public domain

Buckets anzeigen

Dieser Abschnitt der Methode dient nur zu Kontrollzwecken und könnte auch komplett entfallen.

    for (int b = 0; b < BUCKETS; b++)
    {
        System.out.println("Bucket " + b + ":");
        bucket[b].zeigeAn();
        System.out.println();
    }

Buckets in das Hauptarray zurückschreiben

    for (int b = 0; b < BUCKETS; b++)
    {
        for (int i = 0; i < bucket[b].anzahl; i++)
        {
            zahlen[index] = bucket[b].element[i];
            index++;
        }
    }

Beginnend mit dem ersten Bucket (Index b = 0) werden die sortierten Zahlen eines jeden Eimers in das Hauptarray zurückgeschrieben. Die in dem Hauptarray stehenden (alten) Zahlen werden dabei einfach überschrieben - es muss also kein neues Array angelegt werden, sondern das Array wird an Ort und Stelle sortiert.

Achten Sie darauf, dass hier direkt auf die Arrayelemente der einzelnen Bucket-Objekte zugegriffen werden kann. In der Klasse Liste hatten wir den Array element[] sowie die Instanzvariable anzahl nämlich nicht als private deklariert. Daher sind die beiden Instanzvariablen für andere Klassen öffentlich zugänglich. Eine Getter-Methode getElement(int i) ist hier also nicht nötig.

Die Konsolen-Ausgabe

Lassen wir das Programm nun laufen und schauen uns die Konsolen-Ausgabe an:

Anzeigen des unsortierten Arrays
   23   34    5    9   13    6   22   18   57   47
   45    2
Bucket 0:
    2    5    6    9

Bucket 1:
   13   18

Bucket 2:
   22   23

Bucket 3:
   34

Bucket 4:
   45   47

Bucket 5:
   57


Anzeigen des sortierten Arrays
    2    5    6    9   13   18   22   23   34   45
   47   57

Dieses kleine Beispiel zeigt, dass der Bucketsort gut funktioniert. Die sechs Buckets sie wie erwartet mit den passenden Zahlen gefüllt, und man kann auch sehen, dass die Zahlen innerhalb der Buckets sortiert sind.

Experimente mit größeren Arrays

Wir setzen jetzt die beiden Konstanten am Anfang der Klasse Eimer mal auf größere Werte:

    private final int MAX = 100;      // Anzahl Elemente im Hauptarray
    private final int MAXWERT = 200;  // Wertebereich: 1..MAXWERT

Wir wollen also ein Array mit 100 Zahlen im Bereich 0..200 sortieren. Schauen wir uns nun die gekürzte Konsolen-Ausgabe an.

Das unsortierte Array:

   66   80  189   80  160  103   17   26   21   10
   17   70  197   49  149  182   81  172  176   23
   83  116  184  116  162   45   84   63  190   36
   87  124  117   43  113   66  164    6   28  199
  113   97  115   79  141   88  119   24  191  138
  139   60    3  179    7   36  146   21   27   86
  139   50   25  195  103   73   36  192    2   34
   48  158   94  152  167   32  137  114   42  161
  150   61  129   71  169   58   65   80  100   63
  188   95   63   37   15  107  172  134   92  116

Die Buckets 0 bis 5:

Bucket 0:
    2    3    6    7

Bucket 1:
   10   15   17   17

Bucket 2:
   21   21   23   24   25   26   27   28

Bucket 3:
   32   34   36   36   36   37

Bucket 4:
   42   43   45   48   49

Bucket 5:
   50   58

Insgesamt haben wir hier 21 Buckets vorliegen, der letzte Eimer enthält allerdings keine Daten.

Das sortierte Array:

    2    3    6    7   10   15   17   17   21   21
   23   24   25   26   27   28   32   34   36   36
   36   37   42   43   45   48   49   50   58   60
   61   63   63   63   65   66   66   70   71   73
   79   80   80   80   81   83   84   86   87   88
   92   94   95   97  100  103  103  107  113  113
  114  115  116  116  116  117  119  124  129  134
  137  138  139  139  141  146  149  150  152  158
  160  161  162  164  167  169  172  172  176  179
  182  184  188  189  190  191  192  195  197  199

Damit schließen wir unsere Betrachtungen zum Thema "Bucketsort" erst einmal ab. Für Sie gibt es aber noch zwei Aufgaben.

Aufgaben