Folgendes Implementierungsbeispiel in C++ zeigt, wie vorzeichenlose 32-Bit-Werte mittels RadixSort sortiert werden können.
Die Analogie zum Postleitzahlenbeispiel ist in der Form vorhanden, dass nun nicht nach einzelnen Ziffern der Postleitzahlen,
sondern nach einzelnen Bytes der +Integer sortiert wird, der Rest analog!
#include <deque.h>
/* "radixsort" sortiert die Elemente gegebenen Arrays a[0 bis (n-1)].
Das Gesamtlaufzeitverhalten beträgt hier O(256 + 4*(n+max{n,256}))
= O(4*(n+max{n,256}))
= O(n+max{n,256})
= O(max{n,256}), also O(n) für n > 256, andernfalls O(1). */
void radixsort(unsigned int *a, int n)
{
/* Initiierung von 256 Queues (FIFO) */
deque<unsigned int> partition[256]; // Laufzeitverhalten: O(256)
/* 4 Sortiervorgänge = 4 Durchläufe: part in [0, 8, 16, 24]
1. Sortiere nach niederwertigsten Byte (0x000000FF)
2. Sortiere nach nächsthöheren Byte (0x0000FF00)
3. Sortiere nach nächsthöheren Byte (0x00FF0000)
4. Sortiere nach höchstwertigsten Byte (0xFF000000) */
for (int part = 0; part < 32; part += 8) // Laufzeitverh.: O(4*(n+max{n,256}))
{
/* 1. Schritt: die Partitionierungsphase!
Alle n Elemente des Arrays a in die Partition aufnehmen.
Da in den Slots der Partition Kollisionen auftreten können,
wird das aktuelle Element a[i] stets hinten angefügt (push_back). */
for (int i = 0; i < n; i++) // Laufzeitverhalten: O(n)
{
int slot = (a[i] >> part) & 0x000000FF; // Schlüssel abbilden
partition[slot].push_back(a[i]); // a[i] in partition[slot] reinschieben
}
/* 2. Schritt: die Sammelphase!
Alle n Elemente der Partition in stabiler Reihenfolge (FIFO)
wieder in das gegebene Array a zurückschreiben.
Alle 256 Queues werden somit wieder leergeräumt,
der Initiierungszustand wird somit wieder hergestellt. */
int i = 0;
for (int slot = 0; slot < 256; slot++) // Laufzeitverh.: O(max{n,256})
{
while (!partition[slot].empty())
{
a[i++] = partition[slot].front(); // FIFO
partition[slot].pop_front();
}
}
}
}
/* Anwendungsbeispiel:
* ...
* unsigned int values[] = {16777217, 256, 0, 256, 65536, 1, 257, 16777216};
* int count = sizeof(values) / sizeof(*values);
* ...
* radixsort(values, count);
* ...
*/
Der begeisterte Leser kann sich ja mal einen
RadixSort-Algorithmus
für
String-Schlüssel
überlegen.
:-)
Bei derartigen Übungen können Sie sich das Konzept des RadixSorts besser verinnerlichen, also wenn das kein Vorteil ist!