#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef void (*gen)(int*, int);
void generate_random(int*, int);
void generate_sorted(int*, int);
void generate_sorted_reverse(int*, int);
void generate_almost_sorted(int*, int);
void generate_almost_sorted_reverse(int*, int);
void insertionSort(int*, int);
void printArray(int*, int);
double timetest (int*, int, gen);
void swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void generate_random(int* arr, int n) {
    //  You can experiment with the modulo value.
    //  The bigger number the less duplicates in the array.
    for(int i = 0; i < n; ++i) arr[i] = lrand48() % 1000000;
}

void generate_sorted(int* arr, int n) {
    for(int i = 0; i < n; ++i) arr[i] = i;
}

void generate_sorted_reverse(int* arr, int n) {
    for(int i = 0; i < n; ++i) arr[i] = n - i;
}

void generate_almost_sorted(int* arr, int n) {
    //  initialize sorted array
    for(int i = 0; i < n; ++i) arr[i] = i;
    //  Make some swaps to disturb the order
    //  Experiment with different # of swaps
    for(int i = 0; i < 100; ++i) {
        int j = lrand48() % n;
        int k = lrand48() % n;
        while(j == k) k = lrand48() % n;
        swap(&arr[j], &arr[k]);
    }
}

void generate_almost_sorted_reverse(int* arr, int n) {
    //  initialize array sorted in reverse order
    for(int i = 0; i < n; ++i) arr[i] = n - i;
    //  Make some swaps to disturb the order
    //  Experiment with different # of swaps
    for(int i = 0; i < 100; ++i) {
        int j = lrand48() % n;
        int k = lrand48() % n;
        while(j == k) k = lrand48() % n;
        swap(&arr[j], &arr[k]);
    }
}


int partition(int * tab, int l, int h) {
    int pivot = tab[h];
    int i = l;
    int j = i;
    while(j < h) {
        if(tab[j] < pivot) {
            swap(&tab[j], &tab[i]);
            i += 1;
        }
        j += 1;
    }
    swap(&tab[i], &tab[h]);
    return i;
}
void Qsort(int * tab, int l, int h){
    if(l < h) {
        int pivot = partition(tab,l,h);
        Qsort(tab,l,pivot-1);
        Qsort(tab,pivot+1,h);
    }
}

void printArray(int* arr, int n) {
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);
    printf("\n");
}
double timetest (int* arr, int n, gen fgen) {

    clock_t t0, t1;
    fgen(arr, n);

    //  Wait for clock() roll over before starting
    t0 = clock();
    while (t0 == (t1 = clock()));

    t0 = t1;
    Qsort(arr, 0, n-1);
    t1 = clock();

    return (t1 - t0) * (1.0 / CLOCKS_PER_SEC);
}
int main() {

    FILE *output = fopen("wyniki","w");
    srand48(time(0));
    for(int i = 1000;i <= 10000;i += 1000){
        int *arr = malloc(i * sizeof(int));
        double d1 = timetest(arr, i, generate_random);
        fprintf(output, "%12.6f\n","co", d1);
        free(arr);
    }

    return 0;
}