#define _XOPEN_SOURCE
#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);

inline
void swap(int* a, int* b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

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

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

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

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

void insertionSort(int* arr, int n) {
    int i;
for(i = 1; i < n; ++i) {
int x = arr[i];
int j = i - 1;
while(j >= 0 && arr[j] > x) {
arr[j+1] = arr[j];
--j;
}
arr[j+1] = x;
}
}

void Change(int arr[], int x1, int x2){ //swap
    int temp=arr[x1];
    arr[x1]=arr[x2];
    arr[x2]=temp;
}
int Pdivision(int l , int r){
    return (l+(r-1))/2;
}
int Pdivision_r(int l , int r){
    //srand(time(NULL));
    return l + lrand48() % (r - l);
}
int Pdivision_median_of_three (int l , int r){
    int one = l + lrand48() % (r - l);
    int two = l + lrand48() % (r - l);
    int three =  l + lrand48() % (r - l);
    if((two <= one && one <= three) || (two >= one && one >= three)) return one;
    if((one <= two && two <= three) || (one >= two && two >= three)) return two;
    if((two <= three && three <= one) || (two >= three && three >= one)) return three;
    return 0;
}
// int Pdivision_classic( int l, int r){   // nie działa nwm czemu, dla tego przypadku jest osobno quickSort ponizej
  //  return r;                              // l podaje tylko dlatego, żeby zmieniać tylko i wyłącznie nazwe funkcji , lenistwo
//}
int Division(int arr[], int l, int r){
    int key = Pdivision_r(l,r);
    int val = arr[key];
    Change(arr, key, r);    // Swap
    int curr=l;
    for(int i=l;i<r;i++){
        if(arr[i]<val){
            Change(arr, i, curr);
            curr+=1;
        }
    }
    Change(arr, curr, r);
    return curr;
}
void Quicksort(int arr[], int l , int r){
    if(l<r){
        int i = Division(arr, l, r);
        Quicksort(arr, l, i);
        Quicksort(arr, i+1, r);
    }
}
// to dla przypadku gdy pivot to skrajnie największy indeks

/*int partition (int arr[], int low, int high)
{
    int pivot = arr[high]; // pivot
    int i = (low - 1); // Index of smaller element

    for (int j = low; j <= high - 1; j++)
    {
        // If current element is smaller than the pivot
        if (arr[j] < pivot)
        {
            i++; // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}*/

void printArray(int* arr, int n) {
    int i;
for (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, n, sizeof(int), compare);    //funkcja wbudowana
Quicksort(arr, 0, n-1);                 // moja funkcja do pivotów średnia, rand i median_of_3
//quickSort(arr, 0, n - 1);             // do pivota skrajnie najwiekszy indeks
t1 = clock();

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

int main() {
int n;
printf("\n");
//printf("Enter n: ");
scanf("%d", &n);

// allocate array
int *arr = malloc(n * sizeof(int));
if(!arr) {
printf("allocation failed\n");
exit(1);
}

// initialize the randomizer
srand48(time(0));

// sort sample arrays
double d1 = timetest(arr, n, generate_random);
double d2 = timetest(arr, n, generate_sorted);
double d3 = timetest(arr, n, generate_almost_sorted);
double d4 = timetest(arr, n, generate_sorted_reverse);
double d5 = timetest(arr, n, generate_almost_sorted_reverse);

printf("%f\n", /*"Random",*/ d1*1000);
printf("%f\n", /*"Sorted",*/ d2*1000);
printf("%f\n", /*"Almost Sorted",*/ d3*1000);
printf("%f\n", /*"Sorted (reverse)",*/ d4*1000);
printf("%f\n", /*"Almost Sorted (reverse)",*/ d5*1000);

// free memory
free(arr);

return 0;
}