5. Radixsort


[ Zurück zum Inhaltsverzeichnis ]

5.1 Hintergrund


Die Sortierverfahren, welche wir in den bisherigen Kapiteln kennen gelernt haben, stützen sich allesamt auf Schlüsselvergleiche zum Sortieren der Daten, d.h. die Schlüssel als Ganzes werden miteinander verglichen und bei Bedarf getauscht. Die Sortierverfahren, die jetzt behandelt werden sollen, nutzen hingegen die arithmetischen Eigenschaften der Schlüssel aus. Dabei wird angenommen, dass es sich bei den Schlüsseln um Wörter aus einem m-adischen Alphabet handelt (z.B. m=10 für Dezimalzahlen, m=2 für Dualzahlen, m=26 für Wörter über dem lateinischen Alphabet), man die Schlüssel also als m-adische Zahlen auffassen kann. Daher nennt man m auch die Wurzel (engl./lat.: radix) der Schlüsseldarstellung und die darauf aufbauenden Sortieralgorithmen Radixsort-Verfahren.
Diese betrachten die einzelnen Stellen der m-adischen Schlüssel. Bei Dezimalzahlen würde also jede Ziffer, bei Dualzahlen jedes Bit und bei Zeichenketten jedes Zeichen zum Sortieren heran gezogen werden und nicht wie bei anderen Sortierverfahren die Schlüssel an sich. Daher bezeichnet man die Radixsort's auch als digitale Sortieralgorithmen.
Anwendung finden die Radixsort-Verfahren z.B. dort, wo nur nach bestimmten Schlüsselstellen sortiert werden soll - hier wären andere Sortiermethoden machtlos. Anders bei Radixsort: eine mögliche Variante wäre es, eine Bitmaske zu erstellen, die an denjenigen Schlüsselstellen, nach denen sortiert werden soll, eine 1 hat und dann nur diese Stellen in die Sortierung einzubeziehen.
Die hier vorgestellten Verfahren sollen der Einfachheit halber wie in der Computertechnik üblich auf das duale Zahlensystem zurückgreifen, also die einzelnen Bits als Schlüsselstellen betrachten und darauf ihre Sortierungen aufbauen. Dies ist auch sinnvoll, da eigentlich alles, was in einem Digitalrechner dargestellt wird, in Binärzahlen umgewandelt werden kann und moderne Programmiersprachen einfache Operatoren und Möglichkeiten bereitstellen, um auf die einzelnen Binärziffern einer Variablen zugreifen zu können.
Zunächst soll in diesem Kapitel auf Radix Exchange Sort eingegangen werden, welches Quicksort sehr ähnelt, die Schlüssel von links nach rechts bitweise betrachtet und sukzessive nach 0/1 in 2 Gruppen unterteilt, wodurch eine endgültige Sortierung erreicht wird.
Als Zwischenschritt soll dann eine Erläuterung von Bucketsort erfolgen, welches verstanden werden muss für das darauf aufbauende Straight Radix Sort sowie ein lineares Verfahren als Verallgemeinerung dieser digitalen Sortiermethode.

5.2 Bit-Operationen


Da sich die hier vorgestellten Sortierverfahren auf Vergleiche von Bitstellen stützen, ist es unersetzlich, einzelne bzw. mehrere Bits aus einem Schlüssel extrahieren zu können.
Die Programmiersprache C stellt dafür einige Operatoren bereit: mit x<<y und x>>y werden die Bits der Variablen x um y Stellen nach links bzw. rechts verschoben, x&y verknüpft x bitweise UND mit y - dies genügt uns schon, um die beiden benötigten Funktionen zu definieren.

Die erste Funktion getbit() wird von Radix Exchange Sort und Straight Radix Sort verwendet, um den Wert eines Bits an einer bestimmten Stelle zurückzuliefern:

inline unsigned getbit(unsigned x, int k){ return (x>>k)&1; }

k gibt dabei die von rechts gesehene Stelle an, für welche der Bitwert geliefert werden soll, getbit(x,0) würde z.B. den Wert des am weitesten rechts gelegenen Bits zurückgeben.

Die Verallgemeinerung von Straight Radix Sort mit Bucketsort greift auf die folgende Funktion getbits() zurück, welche den Wert mehrerer Bits zurück liefert:

inline unsigned getbits(unsigned x, int k, int j){ return (x>>k)&~(~0<<j); }

Diese Funktion liefert die j Bits zurück, die k Bits von rechts in x angeordnet sind. Kurz zur Erläuterung: ~(~0<<j) stellt eine Maske dar, die aus Einsen auf den am weitesten rechts stehenden j Bitstellen und Nullen auf den übrigen Positionen besteht. Eine logische UND-Verknüpfung dieser Maske mit dem um k Bits nach rechts verschobenen Schlüssel führt dann dazu, dass duch die Nullen in der Maske diese Bits auf jeden Fall 0 sind und die j rechten Bits durch die Einsen in der Maske den Wert des verschobenen Schlüssels erhalten und zurück geliefert werden.
Folgendes Bild illustriert einen Aufruf von getbits() für den gegebenen Schlüssel. k=3 und j=2, sodass die 2 Bits zurück gegeben werden, welche 3 Bits von rechts im Schlüssel angeordnet sind.


5.3 Radix Exchange Sort


Bei diesem, auch als digitales Austausch-Sortierverfahren bekannten Algorithmus, werden die Bits in den Schlüsseln sukzessive von links nach rechts betrachtet. Es ist leicht ersichtlich, dass alle Schlüssel mit führender 0 kleiner sind als Schlüssel mit führender 1. Die Schlüssel werden demnach so umgeordnet, dass zunächst die gesamte Datei betrachtet und nach der am weitesten links stehenden Bitstelle sortiert wird. Das heißt, die Datei wird in 2 Gruppen unterteilt: die linke Gruppe enthält alle Schlüssel, deren gerade betrachtete Bitstelle 0 ist, die rechte enthält die Schlüssel mit den 1-Bits. Rekursiv werden diese beiden Gruppen nun nach dem gleichen Algorithmus geteilt, wobei pro Rekursionsschicht immer die nächste Bitstelle betrachtet wird. Die Rekursion erfolgt solange, bis entweder alle Bitstellen betrachtet wurden oder aber alle Gruppen nur noch aus einem Element bestehen - die Folge gilt dann als eindeutig sortiert.

Radix Exchange Sort ist deutlich erkennbar als "Teile-und-Herrsche"-Algorithmus und kommt dem ebenfalls auf diesem Prinzip beruhenden Quicksort sehr nahe. Wie bei Quicksort wird die Datei erst in 2 Gruppen geteilt, was aus der Verwendung von binären Schlüsselstellen resultiert (2 Gruppen für 0- und 1-Bits). Daraufhin erfolgen getrennt für die linke und rechte Teildatei die beiden rekursiven Aufrufe.
Und so ist die programmiertechnische Realisierung auch erfreulich ähnlich zu der von Quicksort. Wie bei diesem wird das Feld mit zwei Zeigern durchlaufen, die Ganzzahlen auf Arrayindizes darstellen. Der linke Zeiger startet beim linken Rand der Folge nach rechts und hält an, wenn ein Schlüssel gefunden wird, dessen gerade betrachtetes Bit 1 ist. Der rechte Zeiger steht zu Beginn auf dem Ende der Folge und durchläuft diese nach links, bis ein Schlüssel mit einem 0-Bit an der entsprechenden Bitstelle gefunden wird. In diesem Fall werden die Elemente von linkem und rechtem Zeiger miteinander vertauscht. Diese Prozedur läuft solange, bis beide Zeiger aufeinander treffen und hat zur Folge, dass jetzt in der linken Teildatei nur Elemente mit 0-Bits und in der rechten Datei nur Elemente mit 1-Bits an der relevanten Bitstelle enthalten sind. Im Gegensatz zu Quicksort, bei dem das Trennelement willkürlich gewählt werden konnte, handelt es sich bei diesem digitalen Sortierverfahren stets um die Zahl 2b, wenn b die soeben betrachtete Bitstelle ist. Da nicht gesagt ist, dass diese Zahl in der Schlüsselfolge enthalten ist, kann es auch keine Garantie dafür geben, dass wie bei Quicksort durch einen rekursiven Aufruf ein Element seinen endgültigen Platz in der Datei erhält und nicht weiter betrachtet werden muss.
Durch die Ähnlichkeiten mit Quicksort ist es auch nicht verwunderlich, dass der zugehörige Code frapierende Übereinstimmungen aufweist. Hier eine mögliche Variante, deren Aufruf mit radixexchange(a,0,n-1,8*sizeof(int)); für n Elemente und Ganzzahlen (int's) als Schlüssel erfolgt:

inline unsigned getbit(unsigned x, int k){ return (x>>k)&;1; }

void radixexchange(int a[], int l, int r, int b){	//b=von rechts zu betrachtende Bitstelle
    b--;
    int t, i, j;
    if(r>l && b>=0){					//Dateilänge>1 && noch Bitstellen übrig?
        i=l; j=r;					//i=linker Rand, j=rechter Rand
        while(j!=i){					//solange linker nicht rechter Zeiger
            while(getbit(a[i],b)==0 && i<j) i++;	//halte an, wenn 0 von links  gefunden
            while(getbit(a[j],b)!=0 && j>i) j--;	//halte an, wenn 1 von rechts gefunden
            t=a[i]; a[i]=a[j]; a[j]=t;			//tausche beide Elemente
        }
        if(getbit(a[r],b)==0) j++;			//wenn Datei komplett aus 0 bestehend
        radixexchange(a,l,j-1,b);			//Aufruf für linke Teildatei
        radixexchange(a,j,r,b);				//Aufruf für rechte Teildatei
    }
}


Wieder ein paar Worte zur Erklärung des Codes: in der Parameterliste gibt b die von rechts aus gesehene zu betrachende Bitstelle der momentan zwischen l und r befindlichen Datei an. Der Code wird nur ausgeführt, wenn die Länge der aktuellen Datei größer 1 ist und wenn das eben betrachtete Bit nicht aus der Folge rechts herausläuft. Dann werden die beiden Zeiger auf den linken und rechten Rand der Folge gesetzt und die Schleife betreten, die ein Aufteilen in die beiden Teildateien bewirkt. Hier wird zunächst der linke Zeiger solange inkrementiert, bis er auf eine 1 stößt oder auf den rechten Zeiger trifft. Im Gegensatz zu Quicksort ist der zusätzliche Zeigertest hier nötig, da nur ein Bit untersucht wird und man sich nicht auf Marken verlassen kann, um das Durchsuchen mit den Zeigern abzubrechen. Das Gleiche gilt für die zweite innere Schleife, die dann stoppt, wenn ein 0-Bit von rechts gefunden wurde. Sollte dies geschehen sein, so werden die beiden Elemente miteinander vertauscht. Dies ist auch der Fall, wenn die inneren Schleifen aufgrund eines Aufeinandertreffens der beiden Zeiger verlassen worden sind - tut aber nichts zur Sache, in diesem Fall würde nur das Element, bei welchem die Zeiger aufeinander getroffen sind, mit sich selber vertauscht werden, was keine Auswirkungen hat. Sollten die beiden Zeiger auf dem selben Element stehen, so ist eine Teilung der Datei fast abgeschlossen. Links stehen jetzt alle Elemente mit 0 im b-ten Bit, rechts alle Elemente mit einer 1 an der selbigen Stelle. Das Element a[i] ist jetzt das am weitesten links stehende aus der rechten Teildatei, hat also eine 1 an der b-ten Bitstelle. Dies gilt nicht, wenn die Datei an dieser Bitstelle komplett aus Nullen bestanden hat. Der Test direkt nach der äußeren Schleife berücksichtigt diesen Fall und setzt j eine Position weiter, um den ersten rekursiven Aufruf die gesamte Datei berücksichtigen zu lassen.
Da die Datei jetzt geteilt ist, muss die Spaltung nur noch abgeschlossen werden, indem wie bei Quicksort die Rekursionen erfolgen. Kehren diese zurück, so gilt die aktuelle Teildatei als sortiert.

Folgendes Beispiel verdeutlicht einen Durchlauf der Funktion ohne die rekursiven Aufrufe. Dargestellt ist die jeweils b-te Bitstelle der 9 vorhandenen Schlüssel.
1.) Die Ausgangssituation: zu sehen ist das jeweils b-te Bit eines Schlüssels, die beiden Zeiger i und j sind schon initialisiert und zeigen auf den linken sowie rechten Rand der Folge.
2.1) i findet eine 1 auf der nächsten Position, j steht beteits auf einer 0. Die beiden Schleifen brechen deswegen ab und die beiden Schlüssel werden miteinander vertauscht.
2.2) Eine Position weiter findet i wieder eine 1 vor, j muss zwei Positionen nach links gerückt werden, bis es eine 0 vorfindet. Die beiden Elemente werden vertauscht und die Zeiger rücken weiter.
2.3) Wieder muss i nur eine Position weiter und j zwei Positionen zurück gesetzt werden. Nach dem anschließenden Tausch ist die Sortierung der Datei nach dieser Bitstelle fast abgeschlossen.
3.) i wird noch eine Position weiter gesetzt und verharrt dort, da das darauf stehende Bit eine 1 ist. j hat dieselbe Position wie i, wodurch die entsprechende Schleife sofort abbricht. Nach dem harmlosen Tausch des Elementes mit sich selbst wird die äußere Schleife beendet und die Datei ist nach dieser Bitstelle sortiert.

Nachfolgend noch ein kurzes Beispiel, wie ein Testdatenfeld durch den Algorithmus durchlaufen und dabei sortiert wird.

Grüne Bitstellen bedeuten, dass diese vom Algorithmus nicht mehr betrachtet werden. Größere Abstände zwischen den Testdatensätzen sollen die rekursive Abspaltung in 2 Gruppen verdeutlichen. Der Pfeil unter einem Bild soll das derzeit betrachtete Bit b darstellen.
Das erste Bild zeigt die Ausgangssituation: die 6 Datensätze, deren Schlüssel aus je 5 Bits bestehen, liegen unsortiert vor.
Im zweiten Bild wird das erste Bit betrachtet und die Daten so umverteilt, dass 2 Gruppen mit 0- und 1-Bits an dieser ersten Dualziffer entstehen.
Im dritten Bild werden die beiden entstandenen Gruppen getrennt voneinander nach dem 2. Bit von links sortiert. In der ersten Gruppe gibt es gleich eine Abspaltung von einem Element, da dieses das einzige mit einer 0 an dieser Bitstelle ist. Dieses wird aus der weiteren Betrachtung ausgeschlossen, da es eindeutig an seiner endgültigen Position eingeordnet wurde. Auch die zweite Teildatei aus dem vorherigen Bild kann in diesem Schritt eindeutig sortiert werden, da sie aus nur zwei Elementen bestand und diese an der 2. Bitstelle unterschiedliche Werte haben.
In Bild vier werden die 3 übrig gebliebenen Elemente sortiert. Dabei kommt es wieder zu einer eindeutigen Abspaltung eines Elementes und somit bleiben nur noch 2 zu betrachtende Schlüssel übrig.
Das fünfte Bild zeigt die eindeutige Einordnung der letzten zwei Elemente, da die sich in der 4. Bitstelle unterscheiden. Da alle Elemente einen eindeutigen Platz in der Folge bekommen konnten, kann diese nun als sortiert angesehen werden, wozu noch nicht einmal alle Bitstellen betrachtet werden mussten.

Noch ein paar Gedanken zur Effizienz von Radix Exchange Sort: idealerweise würde natürlich wie bei Quicksort eine Datei genau in der Mitte in 2 Teildateien getrennt werden. Das Problem ist, dass durch den Algorithmus auch führende Nullen mit betrachtet werden und diese machen oftmals den halben Schlüssel aus. Erst in den niederwertigeren Bits entscheidet sich dann die endgültige Sortierung der Datei - so kommt es auch häufig vor, dass bei den hohen Bits nur kleine Teildateien abgesprengt werden und somit der Algorithmus nicht effizient arbeiten kann. Laufzeithemmend kommt hinzu, dass bei gleichen Schlüsseln alle Bits dieser Schlüssel betrachtet werden, was zusätzlichen Rechenaufwand erfordert - daher funktioniert Radix Exchange Sort für Dateien mit vielen gleichen Schlüsseln nicht gut. Bei zufälligen Bits in den Schlüsseln arbeitet der Algorithmus allerdings ähnlich gut wie Quicksort, welches hingegen besser an weniger zufällige Situationen angepasst werden kann und im Allgemeinen trotzdem schneller ist.
Zu guter Letzt bleibt noch zu erwähnen, dass sich Radix Exchange Sort genauso wie Quicksort verbessern lässt, indem z.B. die Rekursion beseitigt wird oder kleine Teildateien mittels Insertion Sort behandelt werden.

5.4 Bucketsort


Als Zwischenschritt will ich hier eine stabile Sortiermethode betrachten, die wir für die nachfolgend dargestellten Sortierverfahren benötigen, welche aber nicht auf der binären Darstellung von Schlüsseln beruht. Beim Bucketsort (auch distribution counting/Verteilungszählen oder Sortieren durch Fachverteilung genannt) handelt es sich sogar um einen quasi linearen Sortieralgorithmus, wobei man aufpassen muss, da linear nicht unbedingt heißt, dass es auch schneller arbeitet als z.B. Quicksort.
Effizient funktioniert dieses Verfahren vor allem dann, wenn eine Datei vorliegt, in der die Anzahl unterschiedlicher Schlüssel begrenzt ist, d.h. viele identische Schlüssel vorliegen. Wenn bei n Datensätzen M unterschiedliche Schlüssel existieren und M hinreichend klein ist, kann man Bucketsort anwenden, welches in diesem Fall effektiver ist als z.B. Quicksort. Die Idee besteht darin, dass man zunächst die Datei durchläuft, um die Anzahl der Schlüssel zu jedem der M Werte zu ermitteln. Das Ergebnis dieser Zählung speichert man in einem Array count[], welches natürlich M Elemente aufnehmen muss und dann bei einem zweiten Durchlauf durch die Datei verwendet wird, um die endgültigen Positionen der Schlüssel in der sortierten Datei zu bestimmen und diese in einem Hilfsarray b[] (welches von gleicher Dimension wie das zu sortierende Array a[] sein muss) abzuspeichern. Anschließend muss aus b zurück nach a kopiert werden, will man das Ergebnis hier stehen haben.
Folgender Codeausschnitt realisiert genau das:

for(j=0; j<M; j++) count[j]=0;		//count[] mit 0 initialisieren
for(i=0; i<N; i++) count[a[i]]++;	//Vorkommen der Schlüssel speichern
for(j=1; j<M; j++)
    count[j]=count[j-1]+count[j];	//Positionen im Array bestimmen
for(i=N-1; i>=0; i--)
    b[--count[a[i]]]=a[i];		//in b einordnen, jeweiligen Zähler verringern
for(i=0; i<N; i++) a[i]=b[i];		//auf a zurück speichern


Die erste for-Schleife initialisiert count[] mit 0, in der zweiten for-Schleife erfolgt der erste Durchlauf durch die Datei, wobei die Anzahl der M verschiedenen Schlüssel gezählt und in count[] gespeichert wird. Diese werden in der dritten for-Schleife aufaddiert, um somit die Startpositionen gleicher Schlüssel im sortierten Array festzulegen. In der vierten Schleife erfolgt die eigentliche sortierte Einordnung im Hilfsspeicher b und zu guter Letzt die Rückspeicherung nach a.

Um die Verfahrensweise dieses Einordnens deutlicher zu machen, soll folgendes Beispiel verwendet werden:
1.) Ausgangssituation: wir haben N=9 Schlüssel, wobei es nur M=4 unterschiedliche Werte gibt. Eigentlich müssten diese 0-4 heißen, zur besseren Verdeutlichung wurden sich jedoch mit A, B, C und D benannt.
2.1) Die zweite for-Schleife obigen Codes zählt die Vorkommen der einzelnen Schlüssel und speichert sie in count[]. count[] ist von der Dimension M=4 und kann somit alle Vorkommen unterschiedlicher Werte speichern.
2.2) count[] enthält nun die Anzahl der einzelnen Werte. A ist 3-mal, B 1-mal, C 2-mal und D 3-mal vorhanden. Mit der 3. for-Schleife werden benachbarte count-Werte addiert.
2.3) Durch die Addition ergibt sich folgendes count[]-Feld. Die einzelnen Werte zeigen jetzt im sortierten Array auf eine Position nach dem letzten Vorkommen des damit verbundenen Schlüssels. So ist count[0]=3, der dazu gehörende Schlüssel A kommt 3-mal vor, muss also auf a[0], a[1] und a[2] abgespeichert werden. a[count[0]]=a[3] zeigt somit auf das Element hinter dem letzten Vorkommen von A im sortierten Feld.
3.1) Nun wird die Datei zum zweiten Mal durchlaufen. Unter b[] ist noch einmal illustriert, auf welchen Elementen die count[]-Zeiger stehen. Dieser Durchlauf erfolgt von hinten nach vorn, wobei jedes Element i genommen und an seine Position count[a[i]]-1 im sortierten Array eingeordnet wird. Hier wird z.B. das letzte Element A genommen, count['A']=count[0]=3, sodass A an seine Position count[0]-1=2 eingeordnet wird.
3.2) Der nächste Schlüssel C wird auf seine Position count['C']-1=count[3]-1=5 eingeordnet.
3.3) D wird auf der letzten Position eingeordnet und count[3] dekrementiert.
3.4) Das einzige B in der Folge wird an seine Stelle count[2]-1 eingeordnet.
3.5) Das nächste A kommt auf seine Position count[0]-1=1.
3.6) Das zweite C wird links vom ersten C auf Position count[2]-1=4 kopiert.
3.7) count[3] wird dekrementiert und D an die entsprechende Stelle im Hilfsarray b[] einsortiert.
3.8) Das nächste D kommt ebenso auf seine Position.
3.9) Der letzte fehlende Schlüssel A wird auf die letzte leere Stelle kopiert und die Datei gilt als sortiert.

Das war doch nicht schwer, oder? Schön lässt sich auch erkennen, dass die relative Sortiertheit der einzelnen gleichen Schlüssel erhalten bleibt, da der zweite Durchlauf durch die Datei "von hinten nach vorn" stattfindet. D.h. hätte man die einzelnen A's usw. indiziert mit A1, A2... dann würde diese Reihenfolge auch in der sortierten Datei erhalten bleiben. Dies ist wichtig, da das gleich besprochene Straight Radix Sort davon ausgeht, dass diese Stabilität gegeben ist.

Man könnte sich fragen, warum nicht gezählt wird und dann die einzelnen Schlüssel gleich ohne weitere Betrachtung in das Array einsortiert werden. Man müsste nur den Wert von Schlüssel i kennen und könnte ihn gleich count[i]-mal in das Array schreiben und schon hätte man nach Abarbeitung für alle Schlüssel ein sortiertes Feld. Das kann man bei einstelligen Schlüsseln ruhig machen, Bucketsort findet aber vor allem dort Anwendung, wo die Schlüssel aus mehreren Ziffern bestehen. Z.B. könnte man Dezimalzahlen haben und mit Bucketsort von rechts nach links nach allen Dezimalziffern sortieren lassen, um am Ende ein sortiertes Feld zu haben. Da nur immer in 10 Fächer (für jede der 10 Ziffern 0-9, also M=10) eingeordnet werden muss, ist der zusätzliche Speicheraufwand für count[] auch überschaubar und Bucketsort arbeitet ausreichend schnell. Es muss also davon ausgegangen werden, dass es sich bei dem Wert nur um einen Teil des eigentlichen Schlüssels handelt und dann der ganze Schlüssel an seine Stelle im Array kopiert werden muss. Übrigens: ist M=2, so gleicht die eben beschriebene Vorgehensweise dem Straight Radix Sort, auf welches gleich noch ausführlicher eingegangen werden soll.

5.5 Straight Radix Sort


Dieses Verfahren, auch geradliniges digitales Sortieren genannt, betrachtet die einzelnen Schlüsselbits im Gegensatz zu Radix Exchange Sort von rechts nach links. Dabei werden die Schlüssel bei jedem neuen Bit wieder nach 0 und 1 sortiert, bis alle Bits betrachtet wurden - die Datei gilt als sortiert.
Man muss ein wenig überlegen, um sich von dem Funktionieren dieser Methode zu überzeugen - tatsächlich führt sie nur dann zum Erfolg, wenn der Prozess des Sortierens nach einem Bit stabil ist. Was das heißt, lässt sich schnell erklären: vor der Betrachtung des beispielsweise 3. Bits von rechts ist die Datei bei Straight Radix Sort schon nach den ersten beiden hinteren Bits sortiert. Wird nun nach dem 3. Bit sortiert, so muss die relative Sortiertheit der beiden hinteren Bits erhalten bleiben. Wenn es z.B. zwei Schlüssel gibt, welche im 3. Bit gleich sind, dann muss nach der Sortierung nach diesem Bit der Schlüssel, welcher von den hinteren beiden Bits her kleiner war, immernoch vor dem anderen Schlüssel stehen. Diese Stabilität zu erreichen ist aber nicht schwer, man kann allerdings z.B. nicht die Teil-Methoden verwenden, wie sie bei Quicksort oder Radix Exchange Sort zur Anwendung gekommen sind.
Vielmehr können wir die stabile Methode des Bucketsorts verwenden, um diesen Algorithmus zu implementieren. Die Anzahl an unterschiedlichen Schlüsseln ist dabei M=2 (0 und 1), sodass jeweils in nur 2 Fächer eingeordnet werden muss und sich somit der zusätzliche Speicherbedarf für count[] auf zwei int-Variablen beschränkt, der Speicherbedarf für das Hilfsfeld b aber natürlich noch bei n Elementen liegt. Die generelle Vorgehensweise sollte nicht schwer zu verstehen sein: betrachte die Schlüssel nach ihren Bits für alle Bitstellen von rechts nach links und sortiere nach den einzelnen Bitwerten mit Bucketsort. Führe dies solange aus, bis alle Bitstellen der Schlüssel betrachtet wurden.
Nach dieser Methode lässt sich Straight Radix Sort wie folgt implementieren:

inline unsigned getbit(unsigned x, int k){ return (x>>k)&;1; }

void straightradix(int a[], int N, int bits){
    int i, pass, count[2], b[N];
    for(pass=0; pass<bits; pass++){			//die Bits der Reihe nach betrachten
        count[0]=0; count[1]=0;				//count[] mit 0 initialisieren
        for(i=0; i<N; i++) count[getbit(a[i],pass)]++;	//Vorkommen der Bits speichern
        count[1]+=count[0];				//Position im Array bestimmen
        for(i=N-1; i>=0; i--)
            b[--count[getbit(a[i],pass)]]=a[i];		//in b einordnen, jeweiligen Zähler verringern
        for(i=0; i<N; i++) a[i]=b[i];			//auf a zurück speichern
    }
}


Aufgrund des Bekanntseins von M=2 konnte Bucketsort so abgewandelt werden, dass zwei Schleifen weggefallen sind, was noch ein paar Laufzeitvorteile mit sich bringt. Trotzdem muss man aufpassen: in der derzeitigen Version ist Straight Radix Sort eigentlich nur eines: lahm. Und zwar genau deswegen, weil es absolut jede Bitstelle betrachtet und nicht wie etwa Radix Exchange Sort nur soweit, bis ein Element als definitiv eingeordnet gilt. Zudem wird pro Bitstelle die Datei von Bucketsort zweimal komplett durchlaufen und noch ein drittes Mal zur Rückspeicherung von b[] nach a[]. Dieses Verfahren liegt in seiner Laufzeit auch noch weit hinter Mergesort zurück und ist somit der langsamste zeitoptimale Sortieralgorithmus. Allerdings wird im kommenden Abschnitt eine Verallgemeinerung der Funktion angegeben werden, welche in praxi sogar schneller als Quicksort läuft.

Folgendes kleines Beispiel soll kurz die Arbeitsweise von Straight Radix Sort verdeutlichen:

Schön zu sehen ist, dass die Schlüssel bitweise von rechts nach links betrachtet werden und vor allem, dass die Schlüssel bei jeder Stufe nach den schon betrachteten Bits sortiert sind, was aufgrund des stabilen Bucketsorts möglich ist. Trotzdem ist dies eine sehr zeitaufwändige Variante, weil die Datei wie schon gesagt ganze dreimal von Bucketsort für jedes Bit betrachtet werden muss. Eine Abwandlung dieses Algorithmus' wird nachfolgend gegeben.

5.6 Lineares Sortieren


Das beste Ergebnis, auf das man bei einem Sortierverfahren hoffen kann, ist das der Linearität. Was heißt das?: es bedeutet, dass der Zeitaufwand, der für das Sortieren von n Schlüsseln benötigt wird, linear anwächst, d.h. dass man sich darauf verlassen kann, dass z.B. bei 2*n Daten sich die Laufzeit verdoppelt, bei 4*n verfierfacht usw. und nicht wie z.B. bei den elementaren Sortierverfahren mit O(n2) quadriert.
Ein solches lineares Sortierverfahren kann man leicht effektiv durch eine Abwandlung von oben gegebenem Straight Radix Sort erhalten. Vielmehr verallgemeinert man obige Funktion, wobei die hintergründige Idee ist, dass man statt nur eines Bits in jedem Durchlauf von Bucketsort gleich m Bits betrachtet, wodurch sich die Anzahl der Fächer, auf die verteilt wird, von M=2 auf M=2m erhöht. Dies erfordert natürlich wieder das ursprüngliche Bucketsort, da nicht wie bei M=2 zwei for-Schleifen entfallen können. Außerdem muss zur Extrahierung mehrerer Bits nun die Funktion getbits() verwendet werden, wie sie oben im Abschnitt 5.2 bereits erläutert wurde. Der Vorteil ist, dass man das Feld nicht dreimal für jedes einzelne Bit durchlaufen muss, sondern nur für m Bits. Wie man m optimal wählen kann, wird gleich besprochen, hier erst einmal die verallgemeinerte Funktion von Straight Radix Sort:

inline unsigned getbits(unsigned x, int k, int j){ return (x>>k)&~(~0<<j); }

void linstraightradix(int a[], int N, int bits, int m){
    int M=1, i, j, pass, *count, b[N];
    if(m<=0 || m>bits/2) m=bits/4;				//Fehlerfälle abfangen, auf guten Fall umsetzen
    for(i=0; i<m; i++,M*=2);					//2^m berechnen
    count=(int*)malloc(M*sizeof(int));
    for(pass=0; pass<bits/m; pass++){				//die Bits der Reihe nach betrachten
        for(j=0; j<M; j++) count[j]=0;				//count[] mit 0 initialisieren
        for(i=0; i<N; i++) count[getbits(a[i],pass*m,m)]++;	//Vorkommen der Schlüssel speichern
        for(j=1; j<M; j++)
            count[j]=count[j-1]+count[j];			//Positionen im Array bestimmen
        for(i=N-1; i>=0; i--)
            b[--count[getbits(a[i],pass*m,m)]]=a[i];		//in b einordnen, jeweiligen Zähler verringern
        for(i=0; i<N; i++) a[i]=b[i];				//auf a zurück speichern
    }
    free(count);
}


Folgendes Beispiel soll wieder die Vorgehensweise des Verfahrens verdeutlichen:

Wie beim ursprünglichen Straight Radix Sort werden die Bits von hinten nach vorn betrachtet, nur dass hier eben nicht nur ein Bit pro Durchlauf, sondern m Bits gleichzeitig betrachtet werden, sodass nur bits/m Durchläufe durch die äußere Schleife notwendig sind, um das gegebene Feld zu sortieren. Dadurch wird allerdings auch zusätzlicher Speicher von M=2m für count[] benötigt. Dieser Speicherbedarf ist nicht zu unterschätzen, heißt es doch, dass bei einer Verdopplung von m eine Quadrierung von M und somit des zusätzlichen Speicherplatzes erfolgt. Für m=4 sind z.B. nur 16 zusätzliche int's, für m=16 hingegen schon 65536 Plätze in count[] erforderlich. Noch gravierender fällt natürlich der zusätzliche Platz für das Feld b[] aus, welches genau soviel Elemente wie a[] aufnehmen muss. Das können bei n=10.000.000 Elementen und 32-Bit-int's schonmal über 38MB sein. Der zusätzlich notwendige Speicher für count[] und vor allem b[] ist auch der Hauptnachteil dieses linearen Sortierverfahrens. Steht ausreichend Arbeitsspeicher zur Verfügung, stellt das kaum ein Problem dar, doch zu sortierende Datenbestände sind nicht immer auf Hochleistungsrechnern zu Hause, sodass in diesem Falle arg abgewogen muss, ob der zusätzliche Speicher bereit gestellt werden kann oder ob man nicht doch lieber Quicksort verwenden sollte.

Die Frage aller Fragen ist natürlich: wie groß sollte man m wählen, damit das Sortierverfahren optimal arbeitet? Empirisch habe ich mit einem entsprechenden Programm folgende Zeiten beim Sortieren von 1.000.000 Elementen gemessen:

Natürlich muss m zwischen einschließlich 1 und der Anzahl der Bits im Schlüssel liegen. Diese waren hier bei einer normalen Ganzzahl 32 Bit, allerdings wird schon bei m=28 1GB zusätzlicher Speicher für count[] benötigt, sodass das Programm mit Speicherzugriffsverletzung abbrach. Offensichtlich ist bei m=11 ein Zeit-Minimum erreicht, auch der zusätzliche Speicher hält sich mit 2048 int's für count[] (entspricht 8KB) in Grenzen. Allgemein kann man feststellen, dass ungefähr m=bits/4 zeitoptimal und der Speicheraufwand dabei nicht übermäßig groß ist. Mit dieser Wahl von einem Viertel der Wortlänge wird die Datei viermal von Bucketsort durchlaufen. Die Schlüssel werden als M-adische Zahlen betrachtet, also zur Basis M und es gibt insgesamt 4 (M-adische) Ziffern pro Schlüssel.
Da Bucketsort linear arbeitet und dieses verallgemeinerte Straight Radix Sort mit m=bits/4 genau 4 Durchläufe bei 32-Bit-Schlüsseln erfordert, ist das gesamte Verfahren linear. Das ist es auch mit jedem anderen m, so auch das ursprüngliche Straight Radix Sort, mit m=bits/4 kommt der Geschwindigkeitsvorteil allerdings erst richtig zur Geltung.
Folgende Funktion gibt noch einmal das optimierte Straight Radix Sort mit m=bits/4 an:

inline unsigned getbits(unsigned x, int k, int j){ return (x>>k)&~(~0<<j); }

void linoptstraightradix(int a[], int N, int bits){
    int M=1, m, i, j, pass, *count, b[N];
    m=bits/4;
    for(i=0; i<m; i++,M*=2);					//2^m berechnen
    count=(int*)malloc(M*sizeof(int));
    for(pass=0; pass<bits/m; pass++){				//die Bits der Reihe nach betrachten
        for(j=0; j<M; j++) count[j]=0;				//count[] mit 0 initialisieren
        for(i=0; i<N; i++) count[getbits(a[i],pass*m,m)]++;	//Vorkommen der Schlüssel speichern
        for(j=1; j<M; j++)
            count[j]=count[j-1]+count[j];			//Positionen im Array bestimmen
        for(i=N-1; i>=0; i--)
            b[--count[getbits(a[i],pass*m,m)]]=a[i];		//in b einordnen, jeweiligen Zähler verringern
        for(i=0; i<N; i++) a[i]=b[i];				//auf a zurück speichern
    }
    free(count);
}


Es hat sich bei mehreren Tests dieses Verfahrens empirisch gezeigt, dass der Geschwindigkeitsvorteil gegenüber einem verbesserten Quicksort bei zufälligen Permutationen im Bereich von 30-40% liegt.
Trotzdem sollte man mit Bedacht zwischen den einzelnen Sortierverfahren abwägen: gerade wenn man sich bewusst ist, dass man nicht den meisten Arbeitsspeicher zur Verfügung hat und Millionen von Datensätzen verwalten muss, kann der zusätzliche Speicherbedarf einer kompletten Kopie des zu sortierenden Feldes zum echten Hindernis werden. Deshalb sollte man vor allem auf Produktivsystemen mit Bedacht wählen, bevor man sich entscheidet: meist ist ein auch bei weniger Speicher stabil arbeitendes Quicksort besser als ein schnelleres lineares Sortierverfahren, welches die doppelte Arbeitsspeichermenge beansprucht. Ein weiterer Aspekt ist die Anpassbarkeit von Quicksort auf wohl definierte Probleme: sind die Eingabedaten nicht zufällig, so ist bei dem angepassten Straight Radix Sort mit erheblichen Effektivitätsverlusten zu rechnen.

5.7 Laufzeitbetrachtungen


Die Laufzeit der ersten beiden Radix-Sortierverfahren für das Sortieren von n Schlüsseln mit jeweils b Bits beträgt im Prinzip n*b. Im Wesentlichen bedeutet dies in Abhängigkeit nur von der Variablen n eine Laufzeitkomplexität von n*log(n), wenn davon ausgegangen wird, dass alle Schlüssel verschieden sind (da b in diesem Fall wenigstens log(n) sein muss), jedoch werden gewöhnlich viel weniger als n*b Operationen ausgeführt: bei Radix Exchange Sort, weil es abbricht, wenn ein Schlüssel an einer eindeutigen Position steht, beim verbesserten Straight Radix Sort, weil hier viele Bits gleichzeitig verarbeitet werden können.
Beide Sortierverfahren benötigen also für das Sortieren von n Schlüsseln mit b Bits weniger als n*b Bitvergleiche - d.h. in dem Sinne, dass die benötigte Zeit proportional zur Anzahl der Bits in den Schlüsseln ist, sind die digitalen Sortierverfahren linear - dies folgt auch daraus, dass sich leicht erkennen lässt, dass jedes Bit höchstens einmal betrachtet wird.
Radix Exchange Sort verwendet im Durchschnitt n*lg(n) Bitvergleiche und ist bei zufälligen Folgen mit Quicksort vergleichbar, das grundlegende Straight Radix Sort muss wie schon erwähnt ungefähr n*b Bitvergleiche ausführen - da hier jedoch absolut jedes Bit betrachtet werden muss und das Feld pro Bit dreimal komplett durchlaufen wird, arbeitet es in der Regel sehr viel langsamer als Radix Exchange Sort oder Quicksort.
Die zuletzt betrachtete lineare Version von Straight Radix Sort mit angepasstem m=bits/4 hingegen kann n Schlüssel in bits/4 Durchläufen sortieren, wobei allerdings zusätzlicher Platz für 2m Zähler und einen Puffer für das Umordnen der Datei in der Größe dieser benötigt wird, was das größte Hindernis darstellt. Dafür hat man auf einfache Weise ein lineares Sortierverfahren auf der Hand, welches bei randomisierten Ausgangsfolgen schneller arbeitet als Quicksort und für Aufgaben, für die genügend Speicherplatz zur Verfügung steht und bei denen es primär auf Geschwindigkeit ankommt, bestens geeignet ist.


[ Zurück zum Inhaltsverzeichnis ]

(c) 2004 by RTC, www.linux-related.de
Dieses Dokument unterliegt der GNU Free Documentation License