Coder Wiki | Algorithmen | RadixExchangeSort

RadixExchangeSort ist ein digitales Sortierverfahren - beim digitalen Sortieren müssen folgende Voraussetzungen gegeben sein:

m-adischen Zahlen identischer Länge
Länge ist mindestens logm n bei n zu sortierenden unterschiedlichen Zahlen

Der Algorithmus geht nach dem "Teile und Herrsche"-Prinzip vor und sortiert immer kleinere Teilfolgen durch Einschränken auf einzelne Schlüsselelemente.

In der Laufzeit ist er ähnlich gut wie Quicksort, hat aber den entscheidenden Vorteil, dass er keinen zusätzlichen Speicher benötigt. Im Gegensatz zu Quicksort, kann der Algorithmus außerdem stabil gemacht werden.

Weblinks

http://de.wikipedia.org/wiki/Radixsort
C++ Implementierung für Floats