#include <stdio.h>

#include <time.h>

#include <stdlib.h>


void swap(int *a, int *b) {



    int tmp;

    tmp = *a;

    *a=*b;

    *b=tmp;



}







int randompivot(int a_length) {



    int index_pivot = rand() % a_length;

    //printf("Zufaellig gewaehlter Index: %d\n",index_pivot);

    return index_pivot;

}



int partition(int a[], int a_length) {


    int al[a_length];  // geht mit gcc,
    int ar[a_length];  // für Visual C muß malloc verwendet werden
    int l, r, k, t;



    int index_pivot = randompivot(a_length); // Zufaelliger Index fuer Pivotelement



    int pivot = a[index_pivot]; // Pivotelement wird bestimmt

    swap(&a[index_pivot],&a[a_length-1]); // Pivotelement wird mit letzter Stelle des Arrays getauscht

    index_pivot = a_length-1; // Neuer Pivotindex



   // pivot = a[index_pivot];


    l = 0; r = 0;
    for(k = 0; k < a_length; k++) { // k beginnt ab 0 zu Zaehlen da Pivotelement immer an letzter Stelle steht

        if(a[k] <= pivot) {

            al[l] = a[k];   // Alle Elemente von a[] welsche <= pivotelement sind werden in al[] geschrieben
            l++;
        }
        else {
            ar[r] = a[k]; // Alle > pivot in ar[]
            r++;
        }
    }


    t = 0;
    for(k = 0; k < l-1; k++) {
        a[t] = al[k];       // Schreibt alle Elemente <= pivot links vom Pivotelement zurueck in den ausgangsarray
        t++;
    }
    a[t] = pivot;           // Position t ist nun Index fuer Pivotelement
    index_pivot = t;
    t++;
    for(k = 0; k < r; k++) {
        a[t] = ar[k];       //Schreibt alle Elemente > Pivot rechts vom Pivotelement in Ausgangsarray
        t++;
    }
    return index_pivot;
}



void quicksort(int a[], int links, int rechts) {



    if(links < rechts) {

        int pivot = partition(a, rechts+1);

        quicksort(a, links, pivot-1);

        quicksort(a, pivot+1, rechts);

    }





}

int main() {


    int a[] = {4,1,3,4,6,7,5,5,9,1,3,4,6,7,9,1,2,5,8,5};
    int n = sizeof(a)/sizeof(a[0]);
    int k;

    int l = 0;

    int r = n-1;


    quicksort(a,l,r);


    printf("Daten:\t ");
    for(k = 0; k < n; k++)

        printf("%d ", a[k]);



    printf("\nIndex:\t ");
    for(k = 0; k < n; k++)

        printf("%d ", k);


    return 0;
}