import algds.IOUtils;

public class aufgabe23 {
    static int zähler;
    /* Hilfsmethode: Initialisierung eines Feldes */
    public static int[] init (int elemente)
    {
        int[]feld = new int[elemente];
        for (int i=0;i<elemente;i++)
        feld[i] = (int) (1000*Math.random() );
        return feld;
    }
    /* Hilfsmethode: Ausgabe der Elemente eines Feldes */
    static void print (int[] feld) {
        for (int i = 0; i < feld.length; i++)
        System.out.print (feld[i] + " ");
        System.out.println ();
    }
    static void tauschen (int[] feld, int e1, int e2) {
        int temp = feld[e1];
        feld[e1] = feld[e2];
        feld[e2] = temp;
    }
    //  Implementierung des QuickSort
    //  Hilfsmethode für rekursives Sortieren
    static void qsort (int[] feld, int l, int r) {
        int lo = l, hi = r;
        if (hi > lo) {
            // Pivotelement bestimmen
            int mid = feld[(lo + hi) / 2];

            while (lo <= hi) {
                // Erstes Element suchen, das größer oder gleich dem
                // Pivotelement ist, beginnend vom linken Index
                while ((lo < r) && (feld[lo] < mid))
                ++lo;

                // Element suchen, das kleiner oder gleich dem
                // Pivotelement ist, beginnend vom rechten Index
                while (( hi > l ) && ( feld[hi] > mid))
                --hi;

                // Wenn Indexe nicht gekreuzt --> Inhalte vertauschen
                if (lo <= hi) {
                    tauschen(feld, lo, hi);
                    zähler++;
                    ++lo;
                    --hi;
                }
            }
            // Linke Partition sortieren
            if (l < hi)
            qsort (feld, l, hi);

            // Rechte Partition sortieren
            if (lo < r)
            qsort( feld, lo, r);
        }
    }
    static void quickSort (int[] feld) {
        zähler=0;
        qsort (feld, 0, feld.length - 1);
        System.out.println("Vertauschungen : " + zähler);
    }
    public static void main(String[] args)
    {
        int[] feld = null;
        feld = init(1000);
        System.out.print("Feld mit 1000 ganzzahligen Elementen  : ");
        print (feld);
        quickSort (feld);
        System.out.print("Feld mit Methode QuickSort sortiert  : ");
        print (feld);
        System.out.println("Nochmal mit QuickSort sortiert ");
        quickSort(feld);
    }
}