#include<stdio.h>
#include<conio.h>
#include<windows.h>

#define N 100000

int a[N], i, j, x, w;

//----------------------------------------
void quicksort(int l, int p){
        i = l;
        j = p;
        x = a[(l+p) / 2];
        do{
            while(a[i] < x) i = i+1;
            while(x < a[j]) j = j-1;
            if(i <= j){
                w = a[i];
                a[i] = a[j];
                a[j] = w;
                i = i+1;
                j = j-1;
            }
        }while(i <= j);

        if(l < j) quicksort(l, j);
        if(i < p) quicksort(i, p);
}
//----------------------------------------

double GetTime()
{
  long long f,t;
  QueryPerformanceFrequency((PLARGE_INTEGER)&f);
  QueryPerformanceCounter((PLARGE_INTEGER)&t);
  return (double)t/(double)f;
}


int main(){

    //---------LOSOWY----------------
    srand(time(NULL));
    for(i=0; i<=N; i++) a[i] = rand();
    double one=GetTime();
    quicksort(0, N-1);
    double two=GetTime();
    printf("Losowy: \t%lf\n", (double)(two-one));
    //-------------------------------


        //-------CIAG-STALY---------------
    for(i=0; i<N; i++) a[i] = 3;
    one=GetTime();
    quicksort(0, N-1);
    two=GetTime();
    printf("Ciag staly: \t%lf\n", (double)(two-one));
    //--------------------------------


    //----------CIAG-ROSNACY----------
    for(i=0; i<N; i++) a[i] = i+1;
    one=GetTime();
    quicksort(0, N-1);
    two=GetTime();
    printf("Ciag rosnacy: \t%lf\n", (double)(two-one));
    //--------------------------------


    //----------CIAG-MALEJACY-----------
    for(i=0; i<N; i++) a[i] = N-i;
    one=GetTime();
    quicksort(0, N-1);
    two=GetTime();
    printf("Ciag malejacy: \t%lf\n", (double)(two-one));
    //-----------------------------------


    //---------ROSNACO-MALEJACY-----------
    j = 2;
    for(i=0; i<N; i++){
        if(i < N/2){
            a[i] = j;
            j = j+2;
        }else{
            j = j-2;
            a[i] = j;
        }
    }
    one=GetTime();
    quicksort(0, N-1);
    two=GetTime();
    printf("Ciag ros-mal: \t%lf\n", (double)(two-one));
    //--------------------------------------


    //----------MALEJACO-ROSNACY------------
    j=2*N/2+1;
    for(i=0; i<N; i++){
        if(i<N/2){
            a[i] = j;
            j = j-2;
        }else{
            j=j+2;
            a[i] = j;
        }
    }
    one=GetTime();
    quicksort(0, N-1);
    two=GetTime();
    printf("Ciag mal-ros: \t%lf\n", (double)(two-one));
    //----------------------------------------


    //for(i=0; i<N-1; i++) if(a[i] > a[i+1]){ printf("Nie jest posortowany"); break;}
    //for(i=0; i<N; i++) printf("[%d]: %d\t", i, a[i]);
    getch();
    return 0;
}