#include <stdio.h>
#include <stdlib.h>
#include <time.h>


void bubblesort(int tab[], int n)                //funkcja sortowania b¹belkowego zbudowana iteracyjnie
{
    int i,j;
    for(i=1;i<n;i++){
        for(j=n-1;j>=1;j--){
            if(tab[j]<tab[j-1]){
                int swap;
                swap=tab[j-1];
                tab[j-1]=tab[j];
                tab[j]=swap;
            }
        }
    }
}

void swap(int *first, int *second)
{
    int temporary = *first;
    *first = *second;
    *second = temporary;
}

int partition(int array[], int low, int high)
{
    int pivot = array[low];
    int i = low-1, j = high+1;

    while(i<j) {
        while(array[--j]>pivot)
            ;
        while(array[++i]<pivot)
            ;
        if(i<j)
            swap(&array[i],&array[j]);
    }
    return j;
}

void quicksort(int array[], int low, int high)
{
    if(low<high) {
        int partition_index = partition(array,low,high);
        quicksort(array, low, partition_index);
        quicksort(array, partition_index+1, high);
    }
}

void fill(int tab[], int n)             //funkcja która uzupe³nia tablicê losowymi liczbami z zakresu -10 do 10
{
    srand(time(NULL));
    int i;
    for(i=0;i<n;i++){
        tab[i]=(rand()%21)-10;
    }
}

void fill_zakres(int tab[], int n)
{
    srand(time(NULL));
    int i;

    int a,b,y,z;
    printf("Podaj zakres losowania liczb:\n");
    printf("Od: ");
    scanf("%d", &a);
    printf("Do: ");
    scanf("%d", &b);
    printf("Zakres %d %d\n", a,b);
    y=a;
    z=b;
    if(a<0){
        y=a*(-1);
    }
    if(b<0){
        z=b*(-1);
    }
    printf("y: %d z: %d\n", y,z);

    int x;
    x=y+z+1;
    printf("x: %d", x);

    for(i=0;i<n;i++){
        tab[i]=(rand()%x)+a;
    }
    system("cls");
    printf("Zakres %d %d\n", a,b);

}

void print_tab(int tab[],int n)         //funkcja wypisujuj¹ca zawartoœæ tablicy
{
    int i;
    for(i=0;i<n;i++){
        printf("%d ",tab[i]);
    }
}

int main()
{
    clock_t start,stop;
    double czas;
    int numer;

    while(1){
        system("cls");
        printf("Co chcesz zrobic: \n");

        printf("1.Mierzenie czasu sortowania babelkowego dla n elemenow\n");
        printf("2.Wyswietlenie tablicy przed i po sortowaniu babelkowym dla n elementow\n");
        printf("3.Mierzenie czasu sortowania quicksort dla n elemenow\n");
        printf("4.Wyswietlenie tablicy przed i po sortowaniu quciksort dla n elementow\n");
        printf("5.Zakoncz dzialanie programu \n");
        scanf("%d", &numer);

        if(numer==1){
            system("cls");

            int n;
            printf("Ile liczb wylosowac: ");
            scanf("%d", &n);                                                                    //pobranie od u¿ytkownika iloœci losowanych liczb

            int tab[n];
            fill_zakres(tab,n);                                                                       //uzupe³nienie tablicy

            start = clock();
            bubblesort(tab,n);
            stop = clock();
            czas = (double)(stop-start)/CLOCKS_PER_SEC;                                        //wywo³anie funkcji sortuj¹cej tablice
            printf("Posortowanie metoda babelkowa %d liczb zajmie: %lf s\n",n,czas);
            puts("");
            system("pause");
        }
        else if(numer==2){
            system("cls");
            int n;
            printf("Ile liczb wylosowac: ");
            scanf("%d", &n);                        //pobranie od u¿ytkownika iloœci losowanych liczb

            int tab[n];
            fill_zakres(tab,n);                             //uzupe³nienie tablicy
            puts("\nPrzed sortowaniem :");
            print_tab(tab,n);                     //wypisanie przed wywo³aniem funkcji do sortowania
            puts("");
            puts("Po sortowaniu: ");
            bubblesort(tab,n);                       //wywo³anie funkcji sortuj¹cej tablice
            print_tab(tab,n);                     //ponowne wypisanie tablicy
            puts("");
            system("pause");
        }

         else if(numer==3){
            system("cls");

            int n;
            printf("Ile liczb wylosowac: ");
            scanf("%d", &n);                                                                    //pobranie od u¿ytkownika iloœci losowanych liczb

            int tab[n];
            fill_zakres(tab,n);                                                                       //uzupe³nienie tablicy

            start = clock();
            quicksort(tab,0,n-1);
            stop = clock();
            czas = (double)(stop-start)/CLOCKS_PER_SEC;                                        //wywo³anie funkcji sortuj¹cej tablice
            printf("Posortowanie metoda quicksort %d liczb zajmie: %lf s\n",n,czas);
            puts("");
            system("pause");
         }

         else if(numer==4){
            system("cls");
            int n;
            printf("Ile liczb wylosowac: ");
            scanf("%d", &n);                        //pobranie od u¿ytkownika iloœci losowanych liczb

            int tab[n];
            fill_zakres(tab,n);                             //uzupe³nienie tablicy
            puts("\nPrzed sortowaniem :");
            print_tab(tab,n);                     //wypisanie przed wywo³aniem funkcji do sortowania
            puts("");
            puts("Po sortowaniu: ");
            quicksort(tab,0,n-1);                      //wywo³anie funkcji sortuj¹cej tablice
            print_tab(tab,n);                     //ponowne wypisanie tablicy
            puts("");
            system("pause");
        }


        else if(numer == 5){
            system("cls");
            printf("Zakonczono dzialanie.");
            return 0;
        }
        else{
            system("cls");
            puts("Blad! Podaj odpowiednia wartosc.");
            system("pause");
        }
    }
}