Radixsort

Radixsort ist eine Sortierungsmethode, die Schrittweise anhand von Schlüsselwertteilen, über einen oder mehrere Sortieralgorithmen, das Eingangsfeld ordnet. Jeder Sortierungsschritt muss stabil sein, d.h. die Elementereihenfolge muss im sortierten Fall gleich bleiben. Am häufigsten wird hier Countingsort verwendet. Die Laufzeit hängt von der Anzahl der Sortierungsschritte und den gewählten Algorithmen ab.

Beispiel (Quellcode): radixsort.cpp
Download (Quellcode): radixsort.zip

Transformation

• Ganzzahlen

  Durch die Aufteilung des Schlüsselwertes, hat der darunterliegende Sortieralgorithmus keine Information, ob es sich um positive oder negative Zahlen handelt. Dies kann leicht durch hinzufügen eines Basiswertes geändert werden. Der Basiswert kann auch der kleinste Schlüsselwert sein und kann dann von allen Schlüsselwerten abgezogen werden.

• Fließkommazahlen

  Da Fließkommazahlen einen Exponenten und ein Vorzeichenbit haben, muss hier mit Vorsicht gearbeitet werden. Die Zahl selbst kann als entsprechend große Ganzzahl (binäre Kopie) behandelt werden. Der Exponent selbst ist Vorzeichenbehaftet und würde im Falle von negativen Werten, rückwärts sortieren. Also muss bei negativen Fließkommazahlen der Exponent sowie die Mantisse negiert werden. Danach gelten die gleichen Regeln wie für die Ganzzahlen.

Auswahl der Schlüsselwertteile

Es sind zwei Richtungen möglich, den Schlüsselwert aufzuteilen, vom geringsten Stellenwert zum höchsten und umgekehrt. Beim Start vom geringsten Stellenwert, muss das komplette Feld für den nächsten Sortierungsschritt weiterverwendet werden. Im anderen Fall, können Teilfelder, mit dem selben Präfix, sortiert werden. Beim häufig verwendeten Countingsort als Sortierungsschritt, macht es nur wenig Sinn in Teilfelder zu verwenden, da unnötige Operationen, zum löschen und aufbau des Hilfsfeldes, verschwendet werden würden.

Radixsort wird solange angewendet bis keine Schlüsselwertteile mehr vorhanden sind.

Durch den Beispielcode

Der Beispielcode, enthält eine Templateklasse (C++), die sich nur für natürliche Zahlen eignet:

• die Sortierungsfunktion

  const std::vector<_TYPE>& Sort(const std::vector<_TYPE>& toSort)

  18
  

  Die Eingangsparameter ist das Feld, welches sortiert werden soll. Das Ausgabefeld wird automatisch erstellt.

Codeanmerkungen

1. Der Beispielcode benutzt einen festen Sortieralgorithmus: Countingsort.

2. Der Beispielcode kann nur mit natürlichen Zahlen verwendet werden, da keine Transformation für andere Datentypen, sofern möglich, definiert ist. Negative Zahlen werden "nach hinten" sortiert, da sie binär größer sind.

3. Die Ausrufparameter des Programms werden als sortierende Elemente benutzt:

   for(int n=1; n<argc; n++)
      arrayToSort.push_back(atoi(argv[n]));

   78
   79
   

   So ergibt

   ./radixsort 8 7 6 5 4 3 2 4 5 6 -1 -2 92384098 12398032 92384097 92384099
   

   die Ausgabe

   Radix sort test...
   
     sorted 16 elements:
        1. 2
        2. 3
        3. 4
        4. 4
        5. 5
        6. 5
        7. 6
        8. 6
        9. 7
       10. 8
       11. 12398032
       12. 92384097
       13. 92384098
       14. 92384099
       15. -2
       16. -1