Schlagwort-Archive: LSD

Algorithmen und Datenstrukturen: Der Radix Sort in Java

Der Algorithmus

Der Radix Sort-Algorithmus sortiert Zahlensysteme anhand ihrer Stellen. Der Radix Sort wird daher auch Base Sort genannt. Dies bedeutet, dass je Stelle ein eigenes Sortierverfahren (zumeist Counting Sort weil Wertebereich überschaubar) eingesetzt wird. Man würde also bei 3 Stellen auch 3x sortieren.

Es gibt einen Most- und Least-Significant-Radix-Sort (MSD / LSD Radix Sort). LSD beginnt bei der niedrigsten Stelle (z.B. den Einern) und bewegt sich zu den höheren Stellen (z.B. Zehner, Hunderter). Bei MSD Radix Sort ist das umgekehrt.

Eine wichtige Voraussetzung ist, das man die gleiche Anzahl an Stellen hat (also z.B. 2 (Tupel), 3 (Tripel) oder mehr Stellen). Weiterhin müssen die vorhandenen Elemente in dem Zahlensystem (z.B. Dezimal 0-9) in einer Reihenfolge nach Rang sortierbar sein. D.h. es sollte z.B. klar sein dass ein A vor einem B ist (z.B. durch ASCII-Werte).

Nehmen wir an, wir möchten die Zahlen [170, 45, 75, 90, 802, 24, 2, 66] sortieren:

LSD Radix Sort (von rechts nach links):

  1. Sortierung nach der 1er-Stelle: [170, 90, 802, 2, 24, 45, 75, 66]
  2. Sortierung nach der 10er-Stelle: [802, 2, 24, 45, 66, 170, 75, 90]
  3. Sortierung nach der 100er-Stelle: [2, 24, 45, 66, 75, 90, 170, 802]

    Anwendung: Oft bei der Sortierung von Zahlen und Wörtern verwendet.
    Vorteil: Einfacher zu implementieren und erfordert weniger komplexe Vergleiche.

MSD Radix Sort (von links nach rechts):

  1. Sortierung nach der 100er-Stelle: [170, 24, 2, 45, 66, 75, 802, 90]
  2. Sortierung nach der 10er-Stelle: [2, 24, 45, 66, 75, 90, 170, 802]
  3. Sortierung nach der 1er-Stelle: [2, 24, 45, 66, 75, 90, 170, 802]

    Anwendung: Eignet sich gut für große Zahlenmengen oder lange Zeichenketten.
    Vorteil: Kann effizienter sein, wenn die Daten ungleichmäßig verteilt sind.

Code von LSD Radix Sort

Der folgende Code hat die vergangenen Implementierungen von QuickSort und Counting Sort (ohne Stellensortierung durch Radix / Base Sort) mit einer Zeitmessung in Echtzeit verglichen und muss angepasst werden. Das nachfolgende Beispiel sortiert Dezimalzahlen (also ein Zahlensystem zur Basis 10).

package AlgoDat;

import java.util.Arrays;

public class RadixSort {
    // Zu sortierendes Array
    private static int myArrayRadixSort[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};
    
    public boolean verbose = false;

    // Hält die Klassen als instanziertes Objekt
    @SuppressWarnings("unused")
    private static RadixSort programRadixSort;
    @SuppressWarnings("unused")
    private static HelperUtil helper;

    // Hilfsfunktion für das Ausgeben des Arrays
    public void OutputOfIntArray(int myArray[])
    {
        if (myArray != null)
        {
            for (int i = 0; i < myArray.length; i++) {
                if (i > 0) System.out.print(";");
                System.out.print(myArray[i]);
            }

            System.out.println();
        }
    }

    public void radixSort(int[] arr) 
    { 
        int max = Arrays.stream(arr).max().getAsInt();
        if (verbose) System.out.println("Größte Zahl im Array: " + max);
        
        // Bei Dezimalzahlen muss die Basis 10 genommen werden
        // ... bei Großbuchstaben z.B. die Basis 27
        for (int exp = 1; max / exp > 0; exp *= 10) 
        { 
            if (verbose) System.out.println("Suche " + exp + "er.");
            countingSort(arr, exp); 
        } 
    } 
    
    public void countingSort(int[] arr, int exp) 
    { 
        int n = arr.length; 
        int[] output = new int[n]; 
        int[] count = new int[10]; 
        
        // Alle 10 Elemente mit 0 initialisieren
        for (int i = 0; i < 10; i++) 
        { 
            count[i] = 0; 
        } 
        
        // Histogramm erstellen
        for (int i = 0; i < n; i++) 
        { 
            count[(arr[i] / exp) % 10]++; 
        } 
        
        // Kummuliere, so dass die Anfangspositionen in dem Array stehen
        for (int i = 1; i < 10; i++) 
        { 
            count[i] += count[i - 1]; 
        } 
        
        // Ausgabearray erstellen
        for (int i = n - 1; i >= 0; i--) 
        { 
            output[count[(arr[i] / exp) % 10] - 1] = arr[i]; 
            count[(arr[i] / exp) % 10]--; 
        } 
        
        // Kopiere das neu erstellte Array auf das zu ändernde Array
        for (int i = 0; i < n; i++) 
        { 
            arr[i] = output[i]; 
        } 
    } 
    
    // Konstruktor
    public RadixSort(int[] toSort)
    {
        this.radixSort(toSort);
    }

    // Konstruktor
    public RadixSort()
    {
        System.out.print("Vorher: ");
        this.OutputOfIntArray(myArray);

        this.radixSort(myArray); 
        
        System.out.print("Nachher: ");
        this.OutputOfIntArray(myArray);
    }

    public static void main(String[] args) 
    {
        helper = new HelperUtil();

        // Es gibt 80 Mio Menschen in Deutschland, von denen keiner älter als 120 ist -> Kleiner Wertebereich
        int[] alterDerMenschenInDeutschlandRS = helper.generateIntegerArrayOfSize(80000000, 120);
        int[] alterDerMenschenInDeutschlandQS = alterDerMenschenInDeutschlandRS.clone();
        int[] alterDerMenschenInDeutschlandCS = alterDerMenschenInDeutschlandRS.clone();
        // Erwartung: Da Counting Sort eine lineare Laufzeit hat sollte er bei kleinem Wertebereich am Besten performen
        
        System.out.println("\nEs gibt 80 Mio Menschen in Deutschland, von denen keiner älter als 120 ist -> Kleiner Wertebereich");
        System.out.println("===================================================================");
        
        long startZeitRS = System.nanoTime();
        programRadixSort = new RadixSort(alterDerMenschenInDeutschlandRS);
        long endZeitRS = System.nanoTime();
        System.out.println((endZeitRS-startZeitRS) + " ns (Radix Sort)");
    }
}

Ausgabe

Es gibt 80 Mio Menschen in Deutschland, von denen 
keiner älter als 120 ist -> Kleiner Wertebereich
=======================================================
347584000 ns (Counting Sort)
2544168000 ns (Radix Sort)
3335958900 ns (Quick Sort)

Komplexität: O-Notation (Ordnung)

O(n*l) (l=Länge also bei ABC = Länge: 3 – Anzahl der max. Stellen0)
‣ Sortieren von Strings über einem endlichen Alphabet durch
mehrmaliges Anwenden von Counting Sort.
‣ Angenommen: Alle Wörter haben die Länge
‣ Z.b. Postleitzahlen

Laufzeit von Radix Sort: 𝒪(n), weil l ⋅ n Durchläufe