/**
 * Beschreiben Sie hier die Klasse QuickSort.
 * 
 * @author (Ihr Name) 
 * @version (eine Versionsnummer oder ein Datum)
 */
import java.util.Random;
public class QuickSort
{
    static Random r = new Random();
    static int[] a = new int[10000000];
    // gibt eine zufällige Zahl von 1-50 zurück 
    public static int Zufallszahl(){      
       return r.nextInt(100000 );
    }
    public static void main(){
        // array mit 20 zufallszahlen von 1-50 belegen 
       for (int i = 0; i < a.length; i++){
           a[i] = Zufallszahl();
       }
       /* ausgeben des arrays "a"
       for (int i = 0; i < a.length; i++){
           System.out.print(a[i]);
           System.out.print(",");
       }
       */
       // absatz
       System.out.println();
       long start = System.currentTimeMillis();
       qi(a, 0, a.length -1);
       long ende = System.currentTimeMillis();
       /* ausgeben des arrays "a"
       for (int i = 0; i < a.length; i++){
           System.out.print(a[i]);
           System.out.print(",");
       }
       */ System.out.println();
       System.out.println(ende - start);
    }
    
    public static int[] q(int[] a){
        // 0. Abbrruchbedingung
        if (a.length < 2) return a; 
        // 1. Pivot
        int pivot = a[a.length -1];
        // 2. Elemente kleiner als Pivot zählen 
        int kleiner = 0;
        for (int i = 0; i < a.length - 1; i++){
            if (a[i] < pivot ) kleiner++;
        }
        // 3. Arrays erstellen
        int[] links = new int[kleiner];
        int[] rechts = new int[a.length - kleiner -1];
        // 4. Arrays befüllen
        int r = 0;
        int l = 0;
        for (int i = 0; i< a.length - 1; i ++){
            if (a[i] < pivot){
                links[l] = a[i];
                l++;
            }
            else{
                rechts[r] = a[i]; 
                r++;
            }
        }
        // 5. Arrays rekursiv sortieren
        links = q(links);
        rechts = q(rechts);
        
        // 6. Zusammensetzen 
        for (int i = 0 ; i < links.length; i ++){
            a [i] = links[i];
        }
        a[links.length] = pivot;
        for (int i = 0; i < rechts.length; i++){
            a[links.length + i + 1]= rechts[i];
        }
        return a;
    }
    public static int[] qi(int [] a, int l , int r){
        //Abrruchbedingung 
        if (r-l < 2) return a;
        // pivot 
        int pivot = a[r]; 
        int i = l;
        int j = r -1;
        // vertauschen 
        while (i < j){
            if (a[i] < pivot) i++;
            if (a[j] >= pivot) j--;
            
            if (a[i] >= pivot && a[j] < pivot){
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }
        // pivot an richtige  Stelle
        int stelle = 0;
        if (a[i] > pivot) {
            a[r] = a[i];
            a[i] = pivot;
            stelle = i;
        }
        else {
            a[r] = a[i +1];
            a[i+1] = pivot;
            stelle = i+1;
        }
        // rekursiver Aufruf
        qi(a, l, stelle - 1);
        qi(a, stelle + 1 , r);
        return a; 
    }
}