Das Prinzip des Distributionsort
 

Kommen wir zu der Idee, die sich hinter diesem Algorythmus verbirgt! Nehmen wir als Beispiel Briefe, die nach Postleizahl sortiert werden sollen. Dies könnte man zum Beispiel so tun:
1. Verteilen der Briefe in Fächer anhand der letzten Ziffer
2. Zusammenlegen unter Beibehaltung der bisherigen Ordnung
3. Verteilen aller Briefe anhand der vorletzten Ziffer
4. Zusammenlegen
......... bis zur ersten Ziffer.

Hier die Schritte im Einzelnen:

Briefe vor dem Sortieren:

Brief 1 nach 3 5 0 3 7 Marburg
Brief 2 nach 7 1 6 7 2 Marbach
Brief 3 nach 3 5 2 8 8 Wohratal
Brief 4 nach 3 5 2 8 2 Rauschenberg

 

Briefe sortiert nach der letzten Ziffer:

Brief 2 nach 7 1 6 7 2 Marbach
Brief 4 nach 3 5 2 8 2 Rauschenberg
Brief 1 nach 3 5 0 3 7 Marburg
Brief 3 nach 3 5 2 8 8 Wohratal

 

Briefe sortiert nach der vierten Ziffer:

Brief 1 nach 3 5 0 3 7 Marburg
Brief 2 nach 7 1 6 7 2 Marbach
Brief 4 nach 3 5 2 8 2 Rauschenberg
Brief 3 nach 3 5 2 8 8 Wohratal

 

Briefe sortiert nach der dritten Ziffer:

Brief 1 nach 3 5 0 3 7 Marburg
Brief 4 nach 3 5 2 8 2 Rauschenberg
Brief 3 nach 3 5 2 8 8 Wohratal
Brief 2 nach 7 1 6 7 2 Marbach

 

Briefe sortiert nach der zweiten Ziffer:

Brief 2 nach 7 1 6 7 2 Marbach
Brief 1 nach 3 5 0 3 7 Marburg
Brief 4 nach 3 5 2 8 2 Rauschenberg
Brief 3 nach 3 5 2 8 8 Wohratal

 

Briefe sortiert nach der ersten Ziffer:

Brief 1 nach 3 5 0 3 7 Marburg
Brief 4 nach 3 5 2 8 2 Rauschenberg
Brief 3 nach 3 5 2 8 8 Wohratal
Brief 2 nach 7 1 6 7 2 Marbach

 

Verwandeln wir dieses Prinzip des Briefesortierens in einen Sortieralgorythmus, so ergeben sich zwei Probleme:

Wir können nicht von einem dezimalen Sortierschlüssel ausgehen. Diese Problem lösen wir, indem wir den Schlüssel als eine Folge von Bytes betrachten. Wir benötigen dann 256 Sortierfächer und müssen soviele Durchgänge vorsehen, wie der Schlüssel Bytes hat.
Das Modell der Fächer würde uns zwingen in der Lage zu sein, alle Elemente in jedem Fach aufzunehmen. Bei 256 Fächern würden wir also 256 mal Platz für das gesammte Array benötigen. Dies wäre jedoch alles andere als effizient und könnte bei grossen Datenmengen zu Problemen füren. Deshalb bedient man sich hier eines Tricks. Es werden durch Aufsummieren die Indexgrenzen im zukünftigen Array errechnet. Man benötigt somit lediglich ein Hilfsarray B, das Platz für alle Elemente bietet.

Fangen wir jedoch vorne an! Hier ein Beispiel:

A: S O R T I E R B E I S P I E L

 

Wir zählen in einem Array "Count" das Vorkommen der einzelnen Bytes; dieser Array entspricht also den Fächern.

... 1 ... 3 ... 3 ... 1 ... 1 1 ... 2 2 1 ...
... 66
(B)		 ... 69
(E)		 ... 73
(I)		 ... 76
(L)		 ... 79
(O)		 80
(P)		 ... 82
(R)		 83
(S)		 84
(T)		 ...

 

Nun kommt das zuvor erwähnte Aufsummieren. Wir bilden den Wert eines Elementes von Count als Summe des Wertes des Elements plus den Wert des Vorgäger-Elementes. Auf diese Weise berechnen wir die Anfangspositionen der Fächer, indem wir den Platzbedarf aller vorherigen Fächer addieren.

... 1 ... 4 ... 7 ... 8 ... 9 10 ... 12 14 15 ...
... 66
(B)		 ... 69
(E)		 ... 73
(I)		 ... 76
(L)		 ... 79
(O)		 80
(P)		 ... 82
(R)		 83
(S)		 84
(T)		 ...

 

Jetzt kennen wir jeweils die Positionen im Hilfsarray B der jeweils am weitesten rechts in A vorkommenden Werte. Wenn wir also A von rechts nach links abarbeiten, können wir die Elemente von A nach B umspeichern. Jede benutzte Indexposition muß dabei um eins vermindert werden. Das ist wichtig, wenn gleiche Elemente vorkommen! Damit ergibt sich:

A[15] -> 'L' count['L'] = 8 (-1 = 7) => B[8]:='L'
A[14] -> 'E' count['E'] = 4 (-1 = 3) => B[4]:='E'
A[13] -> 'I' count['I'] = 7 (-1 = 6) => B[7]:='I'
A[12] -> 'P' count['P'] = 10 (-1 = 9) => B[10]:='P'
A[11] -> 'S' count['S'] = 14 (-1 = 13) => B[14]:='S'
A[10] -> 'I' count['I'] = 6 (-1 = 5) => B[6]:='I'
A[9] -> 'E' count['E'] = 3 (-1 = 2) => B[3]:='E'
A[8] -> 'B' count['B'] = 1 (-1 = 0) => B[1]:='B'
A[7] -> 'R' count['R'] = 12 (-1 = 11) => B[12]:='R'
A[6] -> 'E' count['E'] = 2 (-1 = 1) => B[2]:='E'
A[5] -> 'I' count['I'] = 5 (-1 = 4) => B[5]:='I'
A[4] -> 'T' count['T'] = 15 (-1 = 14) => B[15]:='T'
A[3] -> 'R' count['R'] = 11 (-1 = 10) => B[11]:='R'
A[2] -> 'O' count['O'] = 9 (-1 = 8) => B[9]:='O'
A[1] -> 'S' count['S'] = 13 (-1 = 12) => B[13]:='S'

 

Dadurch erhalten wir den Hilfsarray B als

B E E E I I I L O P R R S S T
 

und wir müssen nur noch B nach A umspeichern.

 

 

©Felix Altmann