Theoretische Informatik

Radix Sort

Du hast den Radix Sort aktuell noch nicht wirklich verstanden? Hier zeigen wir dir das Prinzip von dem Sortieralgorithmus und dessen Vorgehensweise. Danach findest du ein ausführliches Beispiel und alle wichtigen Informationen zur Laufzeitkomplexität. Am Ende findest du drei verschiedene Implementierungen: einen allgemeinen Radix Sort Java Code, sowie auch eine iterative Version und abschließend eine rekursive Radix Sort C++ Implementierung.

Inhaltsübersicht

Grundidee

Der Radixsort kann aus dem lateinischen radix = Wurzel; Basis abgeleitet werden. Er ist auch als Distributionsort oder Fachverteilen bekannt. Dabei handelt es sich um ein lineares Sortierverfahren basierend auf dem Counting Sort  und Bucketsort . Es kann entweder stabile out-of-place oder instabile in-place Varianten realisiert werden. Des Weiteren kann zwischen Verfahren unterschiedenen werden. Zum einen das MSD-Verfahren (englisch most significant digit), bei dem die Stelle mit dem höchsten Wert beginnt oder das LSD-Verfahren (englisch least significant digit), bei dem die niedrigste Stelle beginnt und sich zur höchstwertigen Stelle vorarbeitet.

Die Grundidee dahinter ist eigentlich nur, dass wir bei diesem Sortieralgorithmus mit Queues – also Warteschlagen – arbeiten. Das bedeutet, dass wir mit jedem zusätzlichen Schritt eine weitere Sortierinformation erhalten. Das führt im Endeffekt zur fertigen Sortierung. Beim Radixsort bestehen die Schlüssel aus Zeichen eines endlichen Alphabets der zu ordnenden Elemente. Dabei muss eine totale Quasiordnung zwischen den Zeichen des Alphabets vorhanden sein.

Vorgehensweise

Als Prinzip heißt das, dass wir in jedem Durchlauf die einzelnen Elemente durchgehen und dabei nur einen bestimmten Teil davon begutachten. Als Beispiel kannst du dir ein Geburtsdatum vorstellen, welches aus Tag, Monat und Jahr besteht. Dabei starten wir immer beim letzten Element (z.B. das Jahr) und arbeiten uns – Durchlauf für Durchlauf- zum ersten Element (z.B. Tag) in zwei Phasen vor.

Radixsort, Radix Sort
direkt ins Video springen
Radixsort

Partitionierungsphase

In der Partitionierungsphase werden die Daten in das vorhandene Fach aufgeteilt. Dabei gibt es für jedes einzelne Zeichen des jeweiligen Alphabets ein eigenes Fach. Für Buchstaben also beispielweise jeweils ein Fach a, ein Fach b, etc. Wir ordnen dann immer die zusammengehörige Elementreihe entsprechend unseres geprüften Elements in eine passende Spalte ein. Heißt also, wenn wir das dritte Element der Reihe von hinten betrachten, würde „abb“ in das Fach „b“ einsortiert werden.

Sammelphase

Die zweite Phase ist die Sammelphase. Dabei fügen wir die Inhalte der einzelnen Fächer wieder zu einer neu sortierten Liste zusammen, beginnend mit dem Fach mit der niedrigsten Wertigkeit. Dabei ist es wichtig zu beachten, dass die Reihenfolge der Elemente innerhalb der Fächer nicht verändert werden darf.

Das Ganze wird so oft wiederholt, bis alle einzelnen Stellen der Schlüssel einmal geprüft worden sind.

Radix Sort Beispiel

Aber schauen wir uns zum Verständnis einfach mal ein Beispiel an. Dafür nehmen wir die folgende Liste:

253        518        964        214        182        643        722        851        199        430

Radix Sort Beispiel, Radixsort Beispiel
direkt ins Video springen
Radix Sort Beispiel – 1. Durchlauf

Zweiter Durchlauf

Radix Sort Beispiel 2. Durchlauf, Radixsort Beispiel zweiter Vorgang
direkt ins Video springen
Radix Sort Beispiel – 2. Durchlauf

Letzter Durchlauf

Radixsort Beispiel, Radix Sort Beispiel 3
direkt ins Video springen
Radix Sort Beispiel – 3. Durchlauf

Radix Sort Laufzeit

Aber wie sieht es beim Radix Sort mit der Laufzeit aus? Die Laufzeit lässt sich in etwa mit O(l \cdot n) abschätzen. Das l ist dabei die Länge eines Schlüssels, also in unserem Beispiel wäre l = 3. n stellt die Anzahl der zu sortierenden Elemente dar. Entsprechend ist natürlich klar, dass die Laufzeit linear proportional mit der Anzahl der vorhandenen Elemente ist – also n. Eine lineare Laufzeit ist davon abhängig, ob die maximale Länge der zu sortierenden Elemente von Beginn an bekannt ist.

Implementierung – Radix Sort Java

Ein Beispielcode für eine Radix Sort Java-Implementierung kann wie folgt aussehen:

class Radix_Sortieralgorithmus {
  public static void main (String[] args)
  {
    int liste[] = {…};
    int i = liste.length;
    radixsort(liste, i);
    ausgeben(liste, i);
  }
   
  static int maximum(int liste[], int i)
  {
    int max = liste[0];
    for (int a = 1; a < i; a++)
      if (liste[a] > max)
        max = liste[a];
      return max;
  }
   
   
  static void countingsort(int liste[], int i, int faktor)
  {
    int ausgabe[] = new int[i];
    int a;
    int zaehlen[] = new int[10];
    Arrays.fill(zaehlen,0);
     
    for (a = 0; a < i; a++)
      zaehlen[ (liste[a]/faktor)%10 ]++;
    for (a = 1; a < 10; a++)
      zaehlen[a] += zaehlen[a – 1];
       
    for (a = i – 1; a >= 0; a–)
    {
      ausgabe[zaehlen[ (liste[a]/faktor)%10 ] – 1] = liste[a];
      zaehlen[ (liste[a]/faktor)%10 ]–;
    }
     
    for (a = 0; a < i; a++)
      liste[a] = ausgabe[a];
    }
     
    static void radixsort(int liste[], int i)
    {
     
      int m = maximum(liste, i);
       
      for (int faktor = 1; m/faktor > 0; faktor *= 10)
      countingsort(liste, i, faktor);
    }
     
    static void ausgeben(int liste[], int i)
    {
      for (int a=0; a
        System.out.print(liste[a]+“ „);
  }

}

Iterativ – Radix Sort Java

Im Folgenden ist ein Radix Sort Java-Methode zum Sortieren einer Integer-Liste. Bei dem Code werden potenzielle Vorzeichen nicht beachtet und sollte nur bei positiven Zahlen genutzt werden. Zusätzlich wird eine Schleife über alle Bits der Schlüssel bei 32 Bit gesetzt.

public static void radixsort(int[] i) {
  int     nummer;
  int[]   anzahlfach = new int[2];
  int[][] fach  = new int[2][i.length];
  for (int j=0; j<32; j++) {
    anzahlfach[0] = 0;
    anzahlfach[1] = 0;
for (int k=0; k
      nummer = (i[k]>>j)&1;
      fach[nummer][anzahlfach[nummer]++] = i[k];
    }
  System.arraycopy(fach[0], 0, i, 0,       anzahlfach[0]);
  System.arraycopy(fach[1], 0, i, anzahlfach[0], anzahlfach[1]);
  }
}

Rekursiv – Radix Sort C++

Hier wird Beispielcode für eine Radix Sort C++-Implementierung zur Sortierung eines Integer-Arrays oder -Containers dargestellt, die Minimum einen Forward-Iterator enthält.

void radixsort(const ForwardIterator erster, const ForwardIterator letzter, int faktor = 10)
{
  std::map > buckets;
for (ForwardIterator a = erster; a != letzter; ++a) {
if (faktor == 10) buckets[*a%faktor].push_back(*a); else buckets[(*a/(faktor/10)) %10].push_back(*a); } ForwardIterator ersterneu = erster; for (int a = 0; a < 10; ++a) { for (std::vector::const_iterator b = buckets[a].begin(); b != buckets[a].end(); ) *ersterneu++ = *b++; } if (faktor > *std::max(erster, letzter)) { return; } else { faktor *= 10; radixsort(erster, letzter, faktor); } }

 

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.