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)");
    }
}

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)