Quelltext der Seite Radixsort

'''Radixsort''' (von {{laS|radix}} ‚Wurzel‘, ‚Basis‘) oder auch ''Distributionsort'' (von {{enS|distribution}} ‚Verteilung‘), oder im Deutschen ''Fachverteilen'', ist ein lineares [[Sortierverfahren]], das auf [[Countingsort]] oder [[Bucketsort]] basiert. Das Sortierverfahren hat, unter der Voraussetzung, dass die maximale Länge der zu sortierenden Schlüssel von vornherein bekannt ist, eine lineare [[Laufzeit (Informatik)|Laufzeit]]. Die Vorgehensweise eines [[Lochkartensortierer]]s entspricht einem Radixsort.

Bei allen hier vorgestellten Varianten ist die erste Stelle des Schlüssels diejenige mit dem höchsten Rang. Man unterscheidet Verfahren, deren erster Schritt an dieser höchstwertigen Stelle (MSD) (englisch ''most significant digit'') beginnt, dann können Teilstücke, die nach einem Verfahrensschritt weniger als zwei Elemente enthalten, im nachfolgenden Schritt übersprungen werden; und Verfahren, die an der niedrigstwertigen Stelle (LSD) (englisch ''least significant digit'') beginnen und sich zur höchstwertigen Stelle vorarbeiten.

Ferner gibt es [[Stabilität (Sortierverfahren)|stabile]] [[Out-of-place-Algorithmus|out-of-place]] Varianten und in-place Varianten, die jedoch nicht stabil sind.

== Voraussetzungen ==
Bei Radixsort bestehen die Schlüssel der zu sortierenden Daten aus Zeichen eines endlichen [[Alphabet (Informatik)|Alphabets]]. Zusätzlich muss eine [[Quasiordnung#Totale Quasiordnung|totale Quasiordnung]] zwischen den Zeichen des Alphabets bestehen, meist ist es sogar eine [[Totalordnung]]. Damit ähneln die Schlüssel Zahlen in einem [[Stellenwertsystem]] mit der [[Mächtigkeit (Mathematik)|Mächtigkeit]] des Alphabets als Basis (oder Radix). Dies bedeutet, dass vorzeichenlose Zahlen (z.&nbsp;B. unsigned int) direkt verwendet werden können, während bei vorzeichenbehafteten Zahlen (z.&nbsp;B. signed int) das höchstwertige Bit invertiert interpretiert wird. Auch Gleitkommazahlen (z.&nbsp;B. float) lassen sich trivial vom IEEE-Format in eine geeignete Form umwandeln.

Eine zweite Voraussetzung ist, dass die Länge der Schlüssel durch eine von vornherein bekannte Konstante <math>l</math> begrenzt ist, dann ist das Laufzeitverhalten linear in der Anzahl der Elemente.

== Vorgehensweise (mittels Listen) ==
Radixsort besteht aus mehreren Schritten, und jeder Schritt aus zwei Phasen. Die ''Partitionierungsphase'' dient dazu, die Daten auf Fächer aufzuteilen, während in der ''Sammelphase'' die Daten aus diesen Fächern wieder aufgesammelt werden. Beide Phasen werden für jede Stelle des zu sortierenden Schlüssels einmal durchgeführt. Die Anzahl der Schritte ist gleich der (maximalen) Stellenanzahl.

; Partitionierungsphase: In dieser Phase werden die Daten in die vorhandenen Fächer aufgeteilt, wobei für jedes Zeichen des zugrundeliegenden Alphabets ein Fach zur Verfügung steht. In welches Fach der gerade betrachtete Schlüssel gelegt wird, wird durch das an der gerade betrachteten Stelle stehende Zeichen bestimmt. So wird zum Beispiel die Zahl 352 in das Fach 3 gelegt, und die Zahl 41 in das Fach 0, wenn gerade die dritte Stelle von hinten betrachtet wird (und wenn 10 die Basis (Radix) der Zahldarstellung ist).

; Sammelphase: Nach der Aufteilung der Daten in Fächer in Phase 1 werden die Daten wieder eingesammelt und auf einen Stapel gelegt. Hierbei wird so vorgegangen, dass zuerst alle Daten aus dem Fach mit der niedrigsten Wertigkeit eingesammelt werden, wobei die Reihenfolge der darin befindlichen Elemente nicht verändert werden darf. Danach werden die Elemente des nächsthöheren Faches eingesammelt und an die schon aufgesammelten Elemente angefügt. Dies führt man fort, bis alle Fächer wieder geleert wurden.

Diese beiden Phasen werden nun für jede Stelle der Schlüssel wiederholt, wobei mit der letzten Stelle begonnen wird (LSD (englisch ''least significant digit'') Radixsort). Bei jedem Schritt wird dieselbe Anzahl von Fächern benötigt. Und beim letzten Schritt wird die erste Stelle zum Aufteilen verwendet. Nach der letzten Sammelphase sind die Daten aufsteigend sortiert.

{{Anker|MSD}}Alternativ können die Stellen des Schlüssels auch von der höchstwertigen her (MSD (englisch ''most significant digit'') Radixsort) bearbeitet werden. Hierbei sind bei jedem Schritt zu jedem Fach Unterfächer zu bilden. Allerdings benötigen Unterfächer mit weniger als zwei Elementen keine weitere Unterteilung.

== Vorgehensweise (via Countingsort) ==
Darüber hinaus ist ein anderer Ansatz möglich, der ebenfalls zwei Phasen benötigt. Diese Variante erspart sich die Verwaltung von variablen Listen und benötigt zwei Arrays.
; Zählphase:
Zuerst werden die Füllstände der Fächer durch Zählen ermittelt. Das erste Array für stellenweises Countingsort ergibt ein Histogramm über das Alphabet. Danach wird das Histogramm in sein (linksseitiges) Integral umgewandelt (wobei das erste Element stets Null ist).

; Sammelphase:
Nun wird mittels Histogrammintegral jedes Datenelement einmalig an seine finale Position verschoben (final für diese Runde). Dazu muss nach jedem Zugriff auf das Histogrammintegral der jeweilige Zähler inkrementiert werden, da er als Zeiger auf die Schreibposition dient. Das zweite Array dient dem temporären Speichern der Datenelemente und hat den gleichen Speicherbedarf wie das ursprüngliche Datenarray.

== Vorgehensweise (in-place) ==
{{Verbessern}}{{Kommentar}}: Die Funktionsweise ist unvollständig erklärt.
{{Belege fehlen|Beanstandet im Juli 2019}}
Eine weitere Variante ohne zusätzlichen Speicher (in-place) besteht nur aus der Sammelphase, da hier jedes Fach nur 1 Bit breit ist. Das Zählen der beiden Bitzähler entfällt, da die beiden Bitwerte simultan von den beiden Grenzen des Arrays aufgefüllt werden und die beiden Schreibpositionen dabei aufeinander zulaufen. Da dieser Vorgang nicht stabil ist, muss bei der höchstwertigen Stelle ([[Bitwertigkeit|MSB]]) begonnen werden.

== Laufzeit ==
Die Laufzeit des Algorithmus lässt sich durch <math>\mathcal{O}(l \cdot n)</math> ''(siehe [[Landau-Symbole]])'' abschätzen, wobei <math>l</math> die Länge eines Schlüssels und <math>n</math> die Anzahl der zu sortierenden Elemente bezeichnet. Da <math>l</math> für primitive Datentypen wie [[Integer (Datentyp)|Ganzzahlen]] oder [[Gleitkommazahl]]en konstant ist, hat Radixsort für diese Fälle eine Laufzeit, die linear proportional mit der Anzahl der zu sortierenden Elemente zunimmt, womit es besser ist als andere, vergleichsbasierte Sortierverfahren wie beispielsweise [[Quicksort]]. Für variabel-lange Datentypen wie Listen oder Zeichenketten sind Quicksort oder [[Introsort]] jedoch u.&nbsp;U. die bessere Wahl.
Jedoch ist der Aufwand für jeden Vergleich von Zeichenketten auch linear von ihrer (durchschnittlichen) Länge abhängig, da auch hier eine Zerlegung in die maximale Registerbreite (z.&nbsp;B. 64 Bit) stattfinden muss. Streng genommen ist der Aufwand für vergleichsbasierte Sortierverfahren auch proportional zu <math>\mathcal{O}(l)</math>, wobei <math>l</math> hier effektiv kleiner ist.

== Besonderheit ==
Der Radixsort kann entweder stabil (d.&nbsp;h. duplikate Schlüssel treten nach der Sortierung in der gleichen Reihenfolge auf wie in der Ursprungsmenge) oder in-place (d.&nbsp;h. kein zusätzlicher Speicher nötig) realisiert werden.

== Beispiel ==
Es sollen folgende Zahlen geordnet werden:

 124, 523, 483, 128, 923, 584, 9, 54

Zunächst wird nach der letzten Stelle geordnet (LSD Radixsort).

Es beginnt die Partitionierungsphase:
 '''|0| |1| |2| |3| |4| |5| |6| |7| |8| |9|'''
              |   |               |   |
             52'''3''' 12'''4'''             12'''8'''  '''9'''
             48'''3''' 58'''4'''
             92'''3'''  5'''4'''

Für die [[Stabilität (Sortierverfahren)|Stabilität des Verfahrens]] ist es wichtig, dass die angezeigte Reihenfolge der Elemente in den Fächern <code>'''|3|'''</code> und <code>'''|4|'''</code> eingehalten wird.

Es folgt die Sammelphase (Elemente von oben nach unten, von links nach rechts aufsammeln):
 523, 483, 923, 124, 584, 54, 128, 9

Nun wird nach der nächsten Stelle der Zahlen geordnet (zweite Stelle von hinten nach vorne).

Erneute Partitionierungsphase:
 '''|0| |1| |2| |3| |4| |5| |6| |7| |8| |9|'''
  |       |           |           |
  '''0'''9     5'''2'''3          '''5'''4         4'''8'''3
         9'''2'''3                     5'''8'''4
         1'''2'''4
         1'''2'''8
Für das Funktionieren des Verfahrens ist es wichtig, dass die angezeigte Reihenfolge der Elemente in den Fächern <code>'''|2|'''</code> und <code>'''|8|'''</code> eingehalten wird.
Entsprechendes gilt auch für die späteren Schritte.

Nun eine zweite Sammelphase:
 9, 523, 923, 124, 128, 54, 483, 584

Und jetzt wird nach der ersten Stelle geordnet.

Die letzte Partitionierungsphase:
 '''|0| |1| |2| |3| |4| |5| |6| |7| |8| |9|'''
  |   |           |   |               |
 '''0'''09 '''1'''24         '''4'''83 '''5'''23             '''9'''23
 '''0'''54 '''1'''28             '''5'''84

Es folgt die letzte Sammelphase:
 9, 54, 124, 128, 483, 523, 584, 923

Die Zahlen sind nun aufsteigend sortiert.

== Implementierung in Common Lisp ==
Diese [[Common Lisp|Common-Lisp]]-Implementierung sortiert 32-Bit-Ganzzahlen beginnend mit niederwertigsten Bit:
<syntaxhighlight lang="lisp">
(defun radix-sort (list)
  (dotimes (bit 32)
    (let ((zero) (one))
      (dolist (x list)
        (if (logbitp bit x) (push x one) (push x zero)))
      (setq list (nconc (nreverse zero) (nreverse one)))))
  list)
</syntaxhighlight>

== Implementierung in C++ ==
Folgende Implementierung ermittelt zuerst das größte Element im Container. Danach werden analog zum stellenwertigen Zahlensystem zur als Template-Parameter gewählten Basis alle Stellenwerte solange partitioniert, bis die größte Zahl erreicht wurde. Das algorithmische Prinzip funktioniert zu jeder Basis größer als 1, was in diesem Beispiel als C++-Concept erzwungen wird.

<syntaxhighlight lang="c++">
#include <vector>
#include <algorithm>
#include <array>

template<unsigned Base = 10, std::forward_iterator ForwardIt>
	requires (Base > 1) && std::unsigned_integral<std::iter_value_t<ForwardIt>>
void radix_sort(ForwardIt begin, ForwardIt end) {
    using namespace std;

	if(begin == end)
        return;

    using uint_t = iter_value_t<ForwardIt>;
    uint_t max = *max_element(begin, end);
    array<vector<uint_t>, Base> partitions;
    uint_t factor, nextFactor = 1;

	do {
        factor = nextFactor;

        for(ForwardIt it = begin; it != end; ++it)
            partitions[*it / factor % Base].emplace_back(*it);

        for(ForwardIt it = begin; vector<uint_t> &vec: partitions) {
            it = copy(vec.begin(), vec.end(), it);
            vec.clear();
		}
	} while((nextFactor = factor * Base) / Base == factor && nextFactor <= max);
}
</syntaxhighlight>

Über folgende <code>main</code> Funktion kann die obige Implementierung zum Sortieren von Containern wie Arrays von Integern ohne Vorzeichen genutzt werden, die ein Forward-Iterator anbieten. Das Beispiel nutzt abweichend sieben Partitionen.

<syntaxhighlight lang="c++">
#include <iostream>
#include <random>

using namespace std;

int main() {
    mt19937_64 mt;
    uniform_int_distribution<unsigned> uid( 1, 1'000 );
    vector<unsigned> vu;

    for(size_t i = 0; i != 100; ++i)
        vu.emplace_back(uid(mt));

    radix_sort<7>(vu.begin(), vu.end());

    for(unsigned u: vu)
        cout << u << endl;
}
</syntaxhighlight>

== Literatur ==
* [[Donald Knuth]]. ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.2.5: Sorting by Distribution, pp.&nbsp;168–179.
* [[Robert Sedgewick (Informatiker)|Robert Sedgewick]]: ''Algorithms in C++'', third edition, 1998, p. 424–427.
* [http://www.drdobbs.com/architecture-and-design/220300654 V. J. Duvanenko: ''In-Place Hybrid Binary-Radix Sort'', Dr. Dobb’s Journal, 1 October 2009].

== Weblinks ==
* [http://www.linux-related.de/coding/sort/sort_radix.htm Radixsort auf linux-related.de]
* [http://www.stereopsis.com/radix.html Extrem schnelle C++ Implementierung von Radixsort für Gleitkommazahlen]

[[Kategorie:Sortieralgorithmus]]

[[no:Sorteringsalgoritme#Radix-sortering]]