import static java.util.concurrent.TimeUnit.NANOSECONDS;
import java.util.Random;
import java.util.Arrays;
/**
 * Funktionen mit Beispielen zum Sortieren
 * enthaelt: Bubblesort, Insertionsort, Mergesort, Quicksort, Radixsort, Shellsort, Simplesort
 * weitere Sortierverfahren in entsprechender Klasse im Projekt ADT
 * 
 * @author MB
 * @version FEB 2019    
 */
public abstract class Sortieren
{

    private static long[] liste;

    /**
     * listeFuellen befuellt ein Array einer gewaehlten Groesse mit [long]-Werten
     * @param groesse - die Laenge des Array
     * @param kurz - falls [true] werden die Zahlen kurz gehalten (relevant fuer Radixsort)
     */
    private static void listeFuellen(int groesse, boolean kurz){
        liste = new long[groesse];
        long l = 0;
        long a = (long) Math.pow(10,18);
        Random zufall = new Random();
        for (int i = 0; i < groesse; i++){
            l = zufall.nextLong();
            if (l < 0){
                l = l * (-1); // nur positive Longzahlen werden gesucht (noetig wegen der Verwendung von Indices in Radixsort)
            }
            if (kurz){
                l = l / a;
            }
            liste[i] = l;
        }
    }
    
    /**
     * Bubblesort geht die zu sortierende Liste durch, wobei jeweils der betrachtete Platz mit dem folgenden
     * verglichen wird: Ist der gespeicherte Wert groesser, werden die Plaetze vertauscht. Dies wird bei einer Laenge
     * n der Liste n-mal fuer alle n Plaetze getan. Laufzeit n * n.
     */
    public static long bubblesort(int anzahl,boolean kurz){
        listeFuellen(anzahl,kurz);
        long time = System.nanoTime();
        bubblesort(liste);
        return NANOSECONDS.toMillis(System.nanoTime() - time);
    }
    
     public static long[] bubblesort(long[] liste){
        int anzahl = liste.length;
        for (int i = 0; i < anzahl-1; i++){
            for (int j = 0; j < anzahl - 1; j++){
                if (liste[j] > liste[j+1]){
                    long temp = liste[j];
                    liste[j] = liste[j+1];
                    liste[j+1] = temp;
                }
            }
        }
        return liste;
    }
    
    /**
     * Insertionsort geht eine zu sortierende Liste durch, indem bei jedem Element ueberprueft wird, ob es groesser
     * ist als die vorhergehenden. Falls das nicht so ist, wird es an der passenden Stelle vorher eingeschoben.
     * Dies wird fuer eine Liste der Laenge n fuer jedes Element maximal n-mal durchgefuehrt. Laufzeit n * n.
     */
    public static long insertionsort(int anzahl,boolean kurz){
        listeFuellen(anzahl,kurz);
        long time = System.nanoTime();
        insertionsort(liste);
        return NANOSECONDS.toMillis(System.nanoTime() - time);
    }
    
    public static long[] insertionsort(long[] liste){
        int anzahl = liste.length;
        for (int i = 0; i < anzahl; i++){
            boolean inserted = false;
            int j = i;
            while ((j >= 1) && (inserted == false)){
                if (liste[j] < liste[j-1]){
                    long temp = liste[j];
                    liste[j] = liste[j-1];
                    liste[j-1] = temp;
                }
                else {
                    inserted = true;
                }
                j--;
            }
        }
        return liste;
    }
    
    /**
     *  Insertionsort, das ein Sortieren beim erstmaligen Einfuegen einer Zahl vollzieht.
     *  Da hier mit Arrays gearbeitet wird und diese immer auf einen Wert initialisiert sind oder werden,
     *  kommen nur Zahlen in Frage, die kleiner als diese Initialwert sind.
     *  
     *  @param anzahl - Groesse des zurueckgegebenen Arrays und invertierte Obergrenze der Zahlen darin
     *  @return - ein sortiertes Array von negativen Zahlen
     */
    public static long[] insertionsort(int a){
        long[] out = new long[a];
        Random r = new Random();
        long zahl = 0;
        for(int i = 0; i < a; i++){
            int j = 0;
            zahl = (r.nextInt(a) + 1) * -1; // nur negative Zahlen, da das Array mit 0 initialisiert ist
            while(j < a-1 && out[j] < zahl){  // Finden der Stelle zum Einfuegen
                   j++;         // Index j kann maximal a-1 werden bei Array-Laenge a
            }
            for(int k = a-1; k > j; k--){  // Verschieben der Zahlen dahinter von rechts her
                out[k] = out[k-1];
            }
            out[j] = zahl;   // Einfuegen der Zahl an die "freie" Stelle
        }
        return out;
    }
        
    
    /**
     * Mergesort spaltet eine zu sortierende Liste, sortiert dann (rekursiv) die beiden Teillisten. 
     * Diese sortierten Teillisten werden zusammengefuehrt, indem die jeweils ersten Glieder bezueglich der 
     * Groesse verglichen werden. Mergesort verfaehrt also in zwei Schritten: DIVIDE & CONQUER. Laufzeit: n * log n.
     */
    public static long mergesort(int anzahl,boolean kurz){
        listeFuellen(anzahl,kurz);
        long time = System.nanoTime();
        mergesort(liste);
        return NANOSECONDS.toMillis(System.nanoTime() - time);
    }
    
    public static long[] mergesort(long[] liste){
        int laenge = liste.length;
        if (laenge < 2){    // nichts zu sortieren
            return liste;
        }
        long[] out = new long[laenge];  // spaeter auszugebendes sortiertes Array
        // divide
        int haelfte = laenge/2;     // Zur Erinnerung: 7 / 2 = 3
        long[] links = new long[haelfte];
        long[] rechts = null;
        if (laenge % 2 == 0){   // je nachdem ob die Ursprungslaenge eine gerade Zahl ist, muss die Abrundung der Division korrigiert werden
            rechts = new long[haelfte];
        }
        else {
            rechts = new long[haelfte+1];
        }
        for (int j = 0; j < haelfte; j++){  // Fuellen der linken Teilliste
            links[j] = liste[j];
        }
        for (int j = 0; j+haelfte < laenge; j++){   // Fuellen der rechten Teilliste
            rechts[j] = liste[haelfte+j];
        }
        // Rekursion (d.h. letztlich werden Aufspaltungen vorgenommen bis zu elementaren Listen, die dann wieder zusammengefuehrt werden
        links = mergesort(links);
        rechts = mergesort(rechts);
        //conquer
        out = merge(links,rechts);
        return out;
    }
    
    private static long[] merge(long[] links, long[] rechts){
        int laenge = links.length + rechts.length;
        long[] out = new long[laenge];
        int l = 0;
        int r = 0;
        int j = 0;
        // Vergleich der beiden Listen von ihren Anfangspunkten her
        while ((l < links.length) && (r < rechts.length)){
            if (links[l] <= rechts[r]){
                out[j] = links[l];
                l++;
            }
            else {
                out[j] = rechts[r];
                r++;
            }
            j++;
        }
        // falls eine der beiden Liste kuerzer ist als die andere
        while (l < links.length){
            out[j] = links[l];
            l++;
            j++;
        }
        while (r < rechts.length){
            out[j] = rechts[r];
            r++;
            j++;
        }
        return out;
    }
    
    /**
     * Quicksort teilt die zu sortierende Liste mittels der (willkuerlichen) Wahl eines Vergleichselementes
     * aus der Liste in zwei Teillisten der groesseren und der kleineren Elemente, die dann selbst (rekursiv)
     * sortiert werden. Laufzeit durchschnittlich: n * log n, im worst case (umgekehrte Sortierung): n * n.
     */
    public static long quicksort(int anzahl,boolean kurz){
        listeFuellen(anzahl,kurz);
        long time = System.nanoTime();
        quicksort(liste,0,liste.length-1);  // Anfangsaufruf mit der gesamten Laenge der Liste
        return NANOSECONDS.toMillis(System.nanoTime() - time);
    }
    
    /**
     *  Quicksort fuer ein [long]-Array
     *  @param obereGrenze - beim initialen Aufruf = liste.length - 1
     */
    public static long[] quicksort(long[] liste, int untereGrenze, int obereGrenze){
        int links = untereGrenze;
        int rechts = obereGrenze;
        int mitte = (untereGrenze + obereGrenze)/2;
        long pivot = liste[mitte];
        do {
            while (liste[links] < pivot){     // erstes Element suchen, das groesser ist als das pivot-Element
                links = links + 1;
            }
            while (pivot < liste[rechts]){   // das kleiner ist, als das pivot-Element
                rechts = rechts - 1;
            }
            if (links <= rechts){      // die beiden werden vertauscht
                long temp = liste[links];
                liste[links] = liste[rechts];
                liste[rechts] = temp;
                links++;
                rechts--;
            }
        } while (links <= rechts);   // links und rechts haben nach der Schleife ihre Funktion getauscht
        // rekursive Aufrufe
        if (untereGrenze < rechts){    // Basisfall: Laenge < 2
            quicksort(liste,untereGrenze,rechts);  // Aufruf auf einem verkuerzten Teil der Ausgangsliste
        }
        if (links < obereGrenze){
            quicksort(liste,links,obereGrenze);  // Aufruf auf einem verkuerzten Teil der Ausgangsliste
        }
        return liste;
    }
    
    /**
     *  Generisches Quicksort fuer ein [Object]-Array
     */
    public static Object[] quicksort(Object[] liste, int untereGrenze, int obereGrenze){
        int links = untereGrenze;
        int rechts = obereGrenze;
        int mitte = (untereGrenze + obereGrenze)/2;
        if (!(liste[mitte] instanceof Comparable)){
                System.err.println("Das Vergleichsobjekt unterstützt keine Vergleichsoperationen");
                return null;
            }
        Comparable pivot = (Comparable) liste[mitte];
        do {
            while (pivot.compareTo(liste[links]) > 0){     // erstes Element suchen, das groesser ist als das pivot-Element
                links = links + 1;
            }
            while (pivot.compareTo(liste[rechts]) < 0){   // das kleiner ist, als das pivot-Element
                rechts = rechts - 1;
            }
            if (links <= rechts){      // die beiden werden vertauscht
                Object temp = liste[links];
                liste[links] = liste[rechts];
                liste[rechts] = temp;
                links++;
                rechts--;
            }
        } while (links <= rechts);   // links und rechts haben nach der Schleife ihre Funktion getauscht
        // rekursive Aufrufe
        if (untereGrenze < rechts){    // Basisfall: Laenge < 2
            quicksort(liste,untereGrenze,rechts);  // Aufruf auf einem verkuerzten Teil der Ausgangsliste
        }
        if (links < obereGrenze){
            quicksort(liste,links,obereGrenze);  // Aufruf auf einem verkuerzten Teil der Ausgangsliste
        }
        return liste;
    }
    
    /**
     *  Neben den vorgestellten Sortierverfahren gibt es noch viele andere. 
     *  Einige (wie Radixsort) koennen bezueglich der Gesamtlaenge der Eingabe 
     *  (d.h. sowohl der Array-Laenge als auch der Laenge der in einem Index gespeicherten Zahl)
     *  noch schneller sein als obiges Merge- oder Quick-Sort.
     *  Radixsort vergleicht nicht komplette Elemente, sondern vergleicht sie Stueck fuer Stueck
     *  (d.h. liest zunaechst nur die erste Ziffer ein, sortiert nach den entsprechenden Werten in
     *  Teillisten, geht dann rekursiv zur zweiten Ziffer etc.).
     *  Der Aufwand beim folgenden Radixsort haengt also nicht nur von der Laenge n des Eingabearrays,
     *  sondern auch von der Laenge w der Eintraege ab. Die Laufzeit betraegt: 3 * n * w (da jeder
     *  Durchgang 3mal das Array durchlaeuft und w Durchgaenge noetig sind). Ob dies effizienter als
     *  Quicksort ist, haengt damit von w ab (log n koennte kleiner als w sein, etwa bei long-Zahlen).
     *  LSD-Radixsort, das Zahlen von hinten nach vorne per Ziffer vergleicht und sortiert.
    *   Es muss nicht angenommen werden, dass die Zahlen gleich lang sind, denn es wird
    *   ausgehend vom Maximum ermittelt, wieviele Stellen zu vergleichen sind.
    *   @param - das zu sortierende Array
    */
    public static long radixsort(int anzahl,boolean kurz){
        listeFuellen(anzahl,kurz);
        long time = System.nanoTime();
        radixsort(liste);
        return NANOSECONDS.toMillis(System.nanoTime() - time);
    }

    public static long[] radixsort(long[] a){
        int i = 0;
        long m = a[0];
        long exp = 1;
        int n = a.length;
        int index = 0;
        long[] b = new long[n];
        // Identifizieren der laengsten Zahl
        for (i = 1; i < n; i++){
            if (a[i] > m){
                m = a[i];
            }
        }
        // solange das Maximum noch Stellen hat, gibt es etwas zu vergleichen
        while (m / exp > 0)
        {
            // fuer jeden Schritt werden 10 Vergleichskaesten benoetigt
            int[] bucket = new int[10];
            // Zaehlen, wieviele Elemente in einen Kasten gehoeren (d.h. wieviele
            // Zahlen auf diese Ziffer enden)
            for (i = 0; i < n; i++){
                index = (int) ((a[i] / exp) % 10);
                bucket[index]++;
            }
            // Die Kaesten werden akkumuliert, um spaeter die Indexes zu finden: gibt es 7
            // Elemente in den vorherigen Kaesten 1 und 2 muss der hoechste Index fuer ein Element
            // aus dem Kasten 3 um diese 7 verschoben werden (per Addition)
            for (i = 1; i < 10; i++){
                bucket[i] += bucket[i - 1];
            }
            // Ein umsortiertes Array wird erstellt, mittels der Zuordnung aus der Akkumulation,
            // wobei die Elemente aus den Kaesten in umgekehrter Reihenfolge im umsortierten Array
            // auftreten: ist im Kasten 5 die Zahl 12 erscheint das erste entnommende Element
            // am Index 11, das naechste bei 10 etc.
            // 
            for (i = n - 1; i >= 0; i--){
                index = (int) ((a[i] / exp) % 10);
                b[--bucket[index]] = a[i];  // Anzahl im Kasten vor dem Auslesen verringert!  
            }
            // Das umsortierte Array wird in das Originalarray zurueckgeschrieben
            for (i = 0; i < n; i++){
                a[i] = b[i];
            }
            // Der naechste Schritt betrifft die naechste Ziffer, exp wird also erhoeht.
            exp *= 10;        
        }
        return a;
    }    
   
    public static void radixsortMitAusgabe(int anzahl,boolean kurz){
        listeFuellen(anzahl,kurz);
        int i = 0;
        long m = liste[0];
        long exp = 1;
        int index = 0;
        int n = liste.length;
        long[] b = new long[n];
        // Identifizieren der laengsten Zahl
        for (i = 1; i < n; i++){
            if (liste[i] > m){
                m = liste[i];
            }
        }
        int schritt = 1;
        // solange das Maximum noch Stellen hat, gibt es etwas zu vergleichen
        while (m / exp > 0)
        {
            // fuer jeden Schritt werden 10 Vergleichskaesten benoetigt
            int[] bucket = new int[10];
            // Zaehlen, wieviele Elemente in einen Kasten gehoeren (d.h. wieviele
            // Zahlen auf diese Ziffer enden)
            for (i = 0; i < n; i++){
                index = (int) ((liste[i] / exp) % 10);
                bucket[index]++;
            }
            for (i = 0; i < 10; i++){
                System.out.println("Anzahl in Kasten " + i + " = " + bucket[i]);
            }
            // Die Kaesten werden akkumuliert, um spaeter die Indexes zu finden: gibt es 7
            // Elemente in den vorherigen Kaesten 1 und 2 muss der hoechste Index fuer ein Element
            // aus dem Kasten 3 um diese 7 verschoben werden (per Addition)
            for (i = 1; i < 10; i++){
                bucket[i] += bucket[i - 1];
            }
            // Ein umsortiertes Array wird erstellt, mittels der Zuordnung aus der Akkumulation,
            // wobei die Elemente aus den Kaesten in umgekehrter Reihenfolge im umsortierten Array
            // auftreten: ist im Kasten 5 die Zahl 12 erscheint das erste entnommende Element
            // am Index 11, das naechste bei 10 etc.
            // 
            for (i = n - 1; i >= 0; i--){
                index = (int) ((liste[i] / exp) % 10);
                b[--bucket[index]] = liste[i];  // Anzahl im Kasten vor dem Auslesen verringert!  
            }
            // Das umsortierte Array wird in das Originalarray zurueckgeschrieben
            for (i = 0; i < n; i++){
                liste[i] = b[i];
            }
            // Der naechste Schritt betrifft die naechste Ziffer, exp wird also erhoeht.
            exp *= 10;        
            // Ausgabe dieses Schrittes
            System.out.println("Das Array nach Schritt: " + schritt);
            for (i = 0; i < n; i++){
                System.out.println(liste[i]);
            }
            schritt++;
        }  
    }
    
    /**
     * Shellsort ist eine Variation von Insertionsort, bei der ein Element mehrere Stellen ueberspringen
     * kann. Dazu wird eine aeussere Schleife eingefuegt, die zunaechst weiter entlegene Stellen miteinander
     * vergleicht und dann sukzessive naeher gelegene Vergleich vornimmt, so dass die weiten Bewegungen i.d.R. 
     * schon am Anfang (also einmal) erfolgen. Die Laufzeit betraegt eigentlich n * n * n (wegen der dritten 
     * eingebetteten Schleife), jedoch handelt es sich bei den meisten Daten um ein sehr schnelles Verfahren,
     * das nicht nur schneller als Insertionsort laeuft.
     */
    public static long shellsort(int anzahl,boolean kurz){
        listeFuellen(anzahl,kurz);
        long time = System.nanoTime();
        shellsort(liste);
        return NANOSECONDS.toMillis(System.nanoTime() - time);
    }
    
    public static long[] shellsort(long[] liste){
        int n = liste.length;
        for(int gap = n/2; gap >= 1; gap = gap/2){ // Ausgangswert fuer die weiten Vergleiche, wird dann um die Haelfte verkuerzt
            for(int i = gap; i < n; i++){
                long l = liste[i];
                int j = i - gap;
                while((j >= 0) && (l < liste[j])){  // j bleibt > 0, wenn mehrmals kleinere Schritt unternommen werden;
                                                   // kommen wir dann in die Schleife, ruecken weitere Elemente nach
                    long tausch = liste[j];
                    liste[j+gap] = tausch;
                    j = j - gap;
                }
                liste[j + gap] = l; // endgueltiger Landeplatz von l (die letzte Subtraktion im [while] wird rueckgaengig gemacht
            }
        }
        return liste;
    }
    
    /**
     *  Simplesort sucht jeweils das (zum bearbeiteten Index) relative Minimum aus dem Rest der Daten.
     *  Laufzeit: n * n (wobei die aeussere Schleife immer kuerzer wird)
     */
    public static long simplesort(int anzahl,boolean kurz){
        listeFuellen(anzahl,kurz);
        long time = System.nanoTime();
        simplesort(liste);
        return NANOSECONDS.toMillis(System.nanoTime() - time);
    }
    
    public static long[] simplesort(long[] liste){
        int anzahl = liste.length;
        for(int i = 0; i < anzahl-1; i++){
            long min = liste[i];
            for(int j = i+1; j < anzahl; j++){
                if(liste[j] < min){
                    long tausch = min;
                    min = liste[j];
                    liste[j] = tausch;
                }
            }
            liste[i] = min;
        }
        return liste;
    }
    
    /**
     *  gruppiert die Objekte in einem [Object]-Array so, dass nur die Elemente < pivot-Element vor diesem stehen
     *  @param pivot - das Vergleichselement, welches das Interface [Comparable] implementieren muss
     *  @return - das umsortierte Array
     */
    public static Object[] pivotSortierung(Object[] liste, Comparable pivot){
        int links = 0;
        int rechts = liste.length;
        do {
            while (pivot.compareTo(liste[links]) > 0){     // erstes Element suchen, das groesser ist als das pivot-Element
                links = links + 1;
            }
            while (pivot.compareTo(liste[rechts]) < 0){   // das kleiner ist, als das pivot-Element
                rechts = rechts - 1;
            }
            if (links <= rechts){      // die beiden werden vertauscht
                Object temp = liste[links];
                liste[links] = liste[rechts];
                liste[rechts] = temp;
                links++;
                rechts--;
            }
        } while (links <= rechts);  
        return  liste;
    }
    
    /**
     * Counting Sort geht davon aus, dass alle zu sortierenden Werte eine Obergrenze haben,
     * die niedrig genug ist, in entsprechend viele buckets zu sortieren.
     * Beispiel: 10000 Zahlen sind zu sortieren, die alle kleiner 1000 sind.
     * Da nicht mehr Wertzuweisungen erfolgen koennen als Indices m im Array, gilt als
     * Komplexitaet O(max(n,m)) - also eine lineare Laufzeit!
     * 
     * @param liste - das zu sortierende Array
     * @param grenze - die Obergrenze der Zahlengroesse
     */    
    public static long[] countingsort(long[] liste, int grenze){
         if (grenze >= Integer.MAX_VALUE){
             System.err.println("Grenzwert zu hoch für dieses Sortierverfahren.");
             return liste;
         }
         int[] counts = new int[grenze];
         int i = 0;
         for(i = 0; i < liste.length; i++){
             counts[((int)liste[i])]++;  // deswegen der Sicherheitscheck zu Beginn der Methode
         }
         // Neubefuellung des Array in sortierter Reihenfolge
         i = 0;
         for(int j = 0; j < grenze; j++){    // Durchgang durch die buckets
             for(int k = counts[j]; k > 0; k--){
                 liste[i++] = j;  // Index nach dem Einfuegen erhoeht
             }
         }
         return liste;
    }
    
    public static long countingsort(int anzahl,int grenze){
        listeFuellen(anzahl,true);
        long time = System.nanoTime();
        countingsort(liste,grenze);
        return NANOSECONDS.toMillis(System.nanoTime() - time);
    }
    
    /**
     * Sortierverfahren sind auch schon in Java eingebaut
     */
    public static long javaSortieren(int anzahl, boolean kurz){
        listeFuellen(anzahl,kurz);
        long time = System.nanoTime();
        Arrays.sort(liste);
        return NANOSECONDS.toMillis(System.nanoTime() - time);
    }
    
    /**
     * Mit Java 8 steht auch (je nach PC-Architektur) eine schnellere parallele Sortierung zur Verfuegung.
     * Sortiert wird in getrennten Threads!
     */
     public static long javaParallelSortieren(int anzahl, boolean kurz){
        listeFuellen(anzahl,kurz);
        long time = System.nanoTime();
        Arrays.parallelSort(liste);
        return NANOSECONDS.toMillis(System.nanoTime() - time);
    }
}