RadixSort

Das schnellste Sortierverfahren, welches je die Welt erblickte - jedoch mit Vorbehalten!

Einführung

Definition

Der RadixSort, auch DistributionSort oder auch BucketSort genannt, ist ein erstaunlich schnelles Sortierverfahren O(n), welches nicht auf Vergleichen zwischen den Schlüsselwerten der Elemente beruht, sondern die Schlüsselwerte der Elemente auf Indexwerte eines temporären Array abbildet. Intern sortiert RadixSort des Öfteren beispielsweise viermal, wobei die Schlüsselwerte dementsprechend partiell abgebildet werden.
Ein interner Sortiervorgang besteht aus zwei Phasen:
  1. Partitionierungsphase
    In dieser Phase werden alle Elemente des Ausgangsarray in ein temporäres, meist kleineres Array hineingequetscht, d. h. dass an einer Indexposition mehrere Elemente untergebracht werden müssen. Aus diesem Grunde müssen die kollidierenden Elemente an der jeweiligen Indexposition des temporären Array gequeued werden (Schubfachprinzip).
  2. Sammelphase
    Beim Aufsammeln werden die zusammengequetschten Elemente wieder in das Ausgangsarray in stabiler Reihenfolge zurückgeschrieben.
Sind nun alle internen Sortiervorgänge abgeschlossen, so sind alle Elemente des Ausgangsarray sortiert.
Damit die Ordnung der vorhergehenden Sortiervorgänge nicht verloren geht, muss jeder interne Soritervorgang stabil sein, siehe hierzu Sortieren.

Dieses Sortierverfahren hat aber einen Haken:
Sortierverfahren, die auf Vergleichen beruhen, benötigen lediglich eine Schlüsselvergleichsfunktion zum jeweiligen Schlüsseltyp, welche dem Sortieralgorithmus je nach Schlüsseltyp bequem übergeben werden kann. Kommt beispielsweise im Laufe des Wandels ein neuer Schlüsseltyp zu einer Anwendung hinzu, so muss lediglich eine dazugehörige Vergleichsfunktion beigefügt, nicht aber die Struktur des Algorithmus angepasst werden.
Beim RadixSort muss allerdings der Algorithmus auf den jeweiligen Schlüsseltyp zurechtgeschnitten werden, d. h. dass die Struktur des RadixSort−Algorithmus immer von der Domäne bzw. vom Typ insbesondere vom Wertebereich der Schlüssel abhängt. Beispielsweise sieht der RadixSort−Algorithmus für vorzeichenbehaftete Integer−Schlüssel anders aus als der für vorzeichenlose und der für Integer−Schlüssel anders als der für String−Schlüssel, usw.
Dennoch ist es vorstellbar einen generischen RadixSort zu entwickeln, jedoch bei einem Versuch den RadixSort zu verallgemeinern, würde der RadixSort erheblich ineffizienter werden.

Komplexität

Dieses Sortierverfahren garantiert in jedem Falle eine Laufzeitkomplexität von O(n), jedoch mit einer verhältnismäßig hohen Konstante c, so dass man eigentlich O(c * n) notieren sollte.

Intern führt RadixSort sequenziell gleich mehrere Sortiervorgänge aus, wobei bei jedem einzelnen Sortiervorgang jedes Element mindestens zweimal angefaßt werden muss; einmal in der Partitionierungsphase und einmal in der Sammelphase.

RadixSort rentiert sich bei genauerer Betrachtung erst, wenn sehr viele Elemente sortiert werden müssen. Voraussetzung dafür ist, dass der Arbeitsspeicher ausreichend Platz zur Verfügung stellt.

Wenn die besagte Konstante c größer sein sollte als log(n), dann sollte auf herkömmliche Verfahren, die auf Vergleichen beruhen, zurückgegriffen werden wie zum Beispiel QuickSort oder MergeSort.

Zudem gehört RadixSort nicht zur Klasse der In-Placement-Sortierverfahren, d. h. dass die Sortierung nicht auf dem gegebenen Array ablaufen kann. RadixSort benötigt mindestens so viel Speicherplatz wie die Schlüssel der zu sortierenden Elemente benötigen.

Anwendungsbereiche

RadixSort wird typischerweise dann angewendet, wenn die zu sortierenden Elemente aus greifbarer Materie und nicht aus (Software−) Information bestehen.

In den Frühzeiten des Computerzeitalters als noch Lochkarten zur Programmierung von Rechenanlagen verwendet wurden, gebrauchte man schon den RadixSort, um Lochkarten zu sortieren.
Und die Post verwendet den RadixSort, um Briefe bzgl. ihrer Postleitzahlen zu sortieren.

Konkretes Zahlenbeispiel

Fünf Briefe müssen nun bzgl. ihrer Postleitzahlen 94032, 83512, 90459, 56410, 53419 sortiert werden.
  • Sortiere nach Einer

    [0:56410] [1] [2:94032,83512] [3] [4] [5] [6] [7] [8] [9:90459,53419]

    56410, 94032, 83512, 90459, 53419
  • Sortiere nach Zehner

    [0] [1:56410,83512,53419] [2] [3:94032] [4] [5:90459] [6] [7] [8] [9]

    56410, 83512, 53419, 94032, 90459
  • Sortiere nach Hunderter

    [0:94032] [1] [2] [3] [4:56410,53419,90459] [5:83512] [6] [7] [8] [9]

    94032, 56410, 53419, 90459, 83512
  • Sortiere nach Tausender

    [0:90459] [1] [2] [3:53419,83512] [4:94032] [5] [6:56410] [7] [8] [9]

    90459, 53419, 83512, 94032, 56410
  • Sortiere nach Zehntausender

    [0] [1] [2] [3] [4] [5:53419,56410] [6] [7] [8:83512] [9:90459,94032]

    53419, 56410, 83512, 90459, 94032
Dieses Verfahren scheint, sehr aufwendig und umständlich zu sein. Für fünf Briefe ist es in der Tat sehr aufwendig, jedoch für 5.000.000 Briefe dürfte es wohl nichts schnelleres mehr geben. :−)

Implementierung

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!

Implementierung mit C++

#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!

Printversion  www.stefan-baur.de / RadixSort  zuletzt geändert am Sonntag, den 15. März 2009

Copyright (c) 2004-2010 Stefan K. Baur