Allgemeines zum Distributionsort
Der Distributionsort-Algorithmus gehört wie der Bubblesort zu den einfachsten Sortierverfahren. Allerdings wird dieses Verfahren so gut wie nie in der Schule behandelt, obwohl es sehr einleuchtend ist. Die Implementierung ist allerdings nicht ganz so einfach, weil zwei Arrays benötigt werden.
Der Distributionsort ist ein Sortieralgorithmus, der Elemente anhand ihrer Werte direkt in zuvor definierte Kategorien ("Buckets" oder "Bins") verteilt - daher wird er auch manchmal als Bucketsort bezeichnet.
Im Gegensatz zu vergleichsbasierten Verfahren wie dem Bubblesort beruht er nicht auf Paarvergleichen, sondern auf einer direkten Zuordnung der Elemente zu Positionen oder Gruppen.
Dadurch kann der Distributionsort bei bekannten Wertebereichen eine sehr hohe Effizienz erreichen, häufig mit linearer Laufzeit O(n).
Die Grundidee besteht darin, jedes Element gemäß seinem Wert in eine passende Verteilungsschublade einzuordnen und anschließend die Schubladen in der richtigen Reihenfolge auszulesen.
Der Distributionsort - der Algorithmus
Phase 1: Zählphase
Der erste Schritt des Distributionsort
Autor: Ulrich Helmich 11/2025, Lizenz: Public domain
In der ersten Phase des Distributionsorts wird die Häufigkeitsverteilung der vorkommenden Werte ermittelt. Wir gehen dabei von einem Array aus positiven Ganzzahlen aus, dessen Wertebereich eng begrenzt ist; im Beispiel liegen sämtliche Werte zwischen 1 und 10.
Zur Vorbereitung wird ein Hilfsarray (auch Frequenzarray oder Count-Array genannt) angelegt, das für jeden möglichen Schlüsselwert genau ein Element enthält. Jedes Element dieses Hilfsarrays repräsentiert somit einen konkreten Zahlenwert des Hauptarrays.
Anschließend wird das Hauptarray einmal vollständig durchlaufen. Für jedes Element wird der entsprechende Zähler im Frequenzarray inkrementiert. Nach Abschluss dieser Zählphase enthält das Frequenzarray daher die absolute Häufigkeit jedes im Wertebereich möglichen Schlüssels.
Im Beispiel mit dem Array
10 - 8- 3 - 4 - 7 - 2 - 10 - 6 - 5 - 8 - 8 - 3 - 5 - 7 - 3 - 7 - 8 - 5
ergibt sich folgende Verteilung des Vorkommens der Zahlen von 1 bis 10:
0 - 1 - 3 - 1 - 2 - 1 - 3 - 4 - 0 - 2
Phase 2: Ausgabephase
In der zweiten Phase wird aus der zuvor ermittelten Häufigkeitsverteilung das sortierte Array konstruiert. Dazu wird das Frequenzarray der Reihe nach von seinem kleinsten Wert bis zum größten durchlaufen. Für jeden Wert wird die im Frequenzarray gespeicherte absolute Häufigkeit ausgelesen.
Anhand dieser Häufigkeit wird der entsprechende Schlüsselwert genau so oft in das Ergebnisarray eingetragen, wie er im Hauptarray vorkommt. Dadurch entstehen automatisch die korrekte Anzahl identischer Werte und zugleich die richtige Reihenfolge aller Schlüssel.
Diese Phase wird häufig als Rekonstruktionsphase, Distributionsphase oder Ausgabephase bezeichnet.
Der entscheidende Vorteil dieser Phase ist der Folgende: Es sind keine Vergleiche zwischen Elementen nötig. Durch die direkte Verwendung der exakten Häufigkeiten entsteht das sortierte Array in linearer Zeit, proportional zur Summe der Arraylänge und der Größe des Wertebereichs.
Der Java-Quelltext
Zunächst zwei wichtige Methoden:
public void setzeVerteilungZurueck()
{
for (int i=0; i < MAX; i++)
{
verteilung[zahlen[i]]++;
}
}
public void fuelleVerteilung()
{
setzeVerteilungZurueck();
for (int i=0; i < MAX; i++)
{
verteilung[zahlen[i]]++;
}
}
Die Methode setzeVerteilungZurueck() füllt alle Elemente des Frequenzarrays verteilung mit Null-Werten. Dies ist wichtig, falls im laufenden Programm der Distributionsort mehrmals hintereinander ausgeführt werden soll.
Die Methode fuelleVerteilung() führt die erste Phase des Distributionsorts aus, die Zählphase. Es wird gezählt, wie oft jeder Wert des Hauptarrays vorkommt.
Für Sie als Java-Anfänger(in) ist sicherlich die folgende Konstruktion interessant:
verteilung[zahlen[i]]++
Die Indices des Arrays verteilung sind selbst wieder Elemente des Arrays zahlen.
Kommen wir nun zur Methode, die die zweite Phase des Distributionsorts durchführt, nämlich die Rekonstruktion des sortierten Arrays:
public void countingSort()
{
int index = 0;
fuelleVerteilung();
// Für alle möglichen Werte von 1 bis MAX_VAL
for (int wert = 1; wert <= MAX_VAL; wert++)
{
int anzahl = verteilung[wert];
// Fülle den Wert 'anzahl' mal in den Array
for (int i = 0; i < anzahl; i++)
{
zahlen[index] = wert;
index++;
}
}
}
Die Methode trägt hier den Namen countingSort(), was eine gängige Bezeichnung für dieses Sortierverfahren ist – schließlich wird in der ersten Phase die Häufigkeit der einzelnen Werte gezählt.
Zu Beginn wird fuelleVerteilung() aufgerufen, das seinerseits zunächst setzeVerteilungZurueck() ausführt, um das Frequenzarray zu initialisieren.
Anschließend durchläuft eine äußere for-Schleife das Frequenzarray von seinem kleinsten bis zum größten zulässigen Schlüsselwert. Jedes Element des Frequenzarrays gibt an, wie oft der entsprechende Wert im Hauptarray vorkommt.
Steht in dem ersten Element des Frequenzarrays beispielsweise eine 3, dann werden die ersten drei Elemente des Hauptarray mit dem Wert 3 gefüllt. Wenn im zweiten Element des Frequenzarrays eine 2 steht, werden die beiden nächsten Element des Hauptarrays mit dem Wert 2 gefüllt. Falls das dritte Element des Frequenzarrays die Zahl 6 enthält, werden die sechs nächsten Elemente des Hauptarrays mit dem Wert 3 gefüllt und so weiter.
Die Zeile
int anzahl = verteilung[wert];
liest genau diese Häufigkeit aus. Der Wert wert wird anschließend anzahl Mal in den Zielarray geschrieben, was durch die innere Schleife realisiert wird. Auf diese Weise entsteht das sortierte Array vollständig ohne Vergleichsoperationen.
Seitenanfang
Weiter mit dem Selectionsort ...