Radixsort

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Radixsort (von lateinisch Radix ‚Wurzel‘, ‚Basis‘) oder auch Distributionsort (von englisch distribution ‚Verteilung‘), oder im Deutschen Fachverteilen, ist ein lineares, stabiles Sortierverfahren, das out-of-place arbeitet und 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. Eine besondere Bedeutung hatte der Radixsort zu Zeiten der Lochkartensortierer, da er deren Verhalten beschreibt. Es gibt auch lineare in-place Varianten, die jedoch nicht mehr stabil sind.

Voraussetzungen[Bearbeiten | Quelltext bearbeiten]

Bei Radixsort wird davon ausgegangen, dass die Schlüssel der zu sortierenden Daten nur aus Zeichen eines endlichen Alphabets bestehen. Zusätzlich muss eine Totalordnung zwischen den Zeichen des Alphabets bestehen.

Eine zweite Voraussetzung ist, dass die Länge der Schlüssel durch eine von vornherein bekannte Konstante begrenzt ist, da die Anzahl der Stellen pro Schlüssel eine entscheidende Auswirkung auf die Linearität des Laufzeitverhaltens hat.

Vorgehensweise (mittels Listen)[Bearbeiten | Quelltext bearbeiten]

Radixsort besteht aus zwei Phasen, die immer wieder abwechselnd durchgeführt werden. 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 der zu sortierenden Schlüssel einmal durchgeführt. Die Anzahl der Runden ist gleich der 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, wenn gerade die dritte Stelle von hinten betrachtet wird (und sofern 10 als Basis für die Zahldarstellung, d.h. als Radix, gewählt wurde).
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 und in der letzten Iteration die erste Stelle zum Aufteilen verwendet wird. Nach dem Aufsammeln für die erste Stelle der Schlüssel sind die Daten aufsteigend sortiert.

Alternativ können die Stellen des Schlüssels auch von der höchstwertigen her bearbeitet werden, dabei ist jedoch zu beachten, dass in der Sammelphase die Elemente vom höchstwertigen Fach her vereint werden.

Vorgehensweise (via Countingsort)[Bearbeiten | Quelltext bearbeiten]

Es ist auch ein anderer Ansatz möglich, der auch zwei Phasen benötigt. Diese Variante erspart sich die Verwaltung von variablen Listen und benötigt zwei Arrays.

Zählphase

Zuerst werden die Füllstande 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)[Bearbeiten | Quelltext bearbeiten]

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.

Laufzeit[Bearbeiten | Quelltext bearbeiten]

Die Laufzeit des Algorithmus lässt sich durch (siehe Landau-Symbole) abschätzen, wobei die Länge eines Schlüssels und die Anzahl der zu sortierenden Elemente bezeichnet. Da für primitive Datentypen mit konstanter Größe wie Ganzzahlen oder Gleitkommazahlen 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. Wenn jedoch nicht konstant ist, wie bei der Sortierung von mutablen Datentypen wie beispielsweise Listen oder Zeichenketten, sind Quicksort oder Introsort 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. B. 64 Bit) stattfinden muss. Streng genommen ist der Aufwand für vergleichsbasierte Sortierverfahren auch proportional zu , wobei m hier effektiv kleiner ist (typischerweise ungefähr um den Faktor 4).

Besonderheit[Bearbeiten | Quelltext bearbeiten]

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

Beispiel[Bearbeiten | Quelltext bearbeiten]

Es sollen folgende Zahlen geordnet werden:

124, 523, 483, 128, 923, 584

Zunächst wird nach der letzten Stelle geordnet.

Es beginnt die Partitionierungsphase:

|0| |1| |2| |3| |4| |5| |6| |7| |8| |9|
             |   |               |
            523 124             128
            483 584 
            923

Es folgt die Sammelphase (Elemente von links nach rechts, von oben nach unten aufsammeln):

523, 483, 923, 124, 584, 128

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|
         |                       |
        523                     483
        923                     584
        124
        128

Nun eine zweite Sammelphase:

523, 923, 124, 128, 483, 584

Und jetzt wird nach der ersten Stelle geordnet.

Die letzte Partitionierungsphase:

|0| |1| |2| |3| |4| |5| |6| |7| |8| |9|
     |           |   |               |
    124         483 523             923
    128             584

Es folgt die letzte Sammelphase:

124, 128, 483, 523, 584, 923

Die Zahlen sind nun aufsteigend sortiert.

Implementierung[Bearbeiten | Quelltext bearbeiten]

iterativ[Bearbeiten | Quelltext bearbeiten]

Java-Methode zum Sortieren von Integer-Arrays:

// Achtung: Integer ist in Java immer vorzeichenbehaftet (=signed).
// Der folgende Code sortiert jedoch so, als ob der Datentyp int kein Vorzeichen hätte (=unsigned)
// und funktioniert daher in Java nur bei positiven Zahlen.

 public static void radixSort(int[] a) {
     int     n;                             // Fachnummer
     int[]   nPart = new int[2];            // Anzahl der Elemente in den beiden Faechern
     int[][] part  = new int[2][a.length];  // die beiden Faecher haben die Groesse des Arrays a
 
     // Schleife ueber alle Bits der Schluessel (bei int: 32 Bit)
     for (int i=0; i<32; i++) {
         nPart[0] = 0;
         nPart[1] = 0;
 
         // Partitionierungsphase: teilt "a" auf die Faecher auf
         for (int j=0; j<a.length; j++) {
             n = (a[j]>>i)&1;              // ermittelt die Fachnummer: 0 oder 1                   
             part[n][nPart[n]++] = a[j];   // kopiert j-tes Element ins richtige Fach
         }
 
         // Sammelphase: kopiert die beiden Faecher wieder nach "a" zusammen
         System.arraycopy(part[0], 0, a, 0,        nPart[0]);
         System.arraycopy(part[1], 0, a, nPart[0], nPart[1]);
     }
 }

rekursiv[Bearbeiten | Quelltext bearbeiten]

C++ Funktion zum Sortieren von Integerarrays und -Containern, die mindestens einen Forward-Iterator anbieten:

#include <algorithm>
#include <map>
#include <vector>

template <typename ForwardIterator>
void radixsort(const ForwardIterator first, const ForwardIterator last, int factor = 10)
{
   // partitionieren
   std::map<int, std::vector<int> > buckets;
   for (ForwardIterator i = first; i != last; ++i) {
      // die gewünschte Ziffer ermitteln und im Bucket mappen
      if (factor == 10) buckets[*i%factor].push_back(*i);
      else buckets[(*i/(factor/10)) %10].push_back(*i);
   }

   // sammeln
   ForwardIterator copyfirst = first;
   for (int i = 0; i < 10; ++i) {
      for (std::vector<int>::const_iterator it = buckets[i].begin(); it != buckets[i].end(); )
         // Sammeln und Änderungen auf den Iteratorbereich [first, last) anwenden
         *copyfirst++ = *it++;
   }


   if (factor > *std::max_element(first, last)) {
      factor = 10;
      return;
   } else {
      factor *= 10;
      radixsort(first, last, factor);
   }
}

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]