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…