#include <iostream>
#include <time.h>
#include <windows.h>

using namespace std;

int ile;
clock_t start,stop;
double czas;

void sortowanie_babelkowe(int *tab, int n)
{
    for(int i=1;i<n;i++)
    {
        for(int j=n-1; j>=1; j--)
        {
            if(tab[j]<tab[j-1])
            {
                int bufor;
                bufor=tab[j-1];
                tab[j-1]=tab[j];
                tab[j]=bufor;
            }
        }
    }
}

void quick_sort(int *tablica, int lewy, int prawy)
{
    int v=tablica[(lewy+prawy)/2];  //obrana os
    int i,j,x;
    i=lewy;
    j=prawy;
    do {
        while(tablica[i]<v) i++;
        while(tablica[j]>v) j--;
        if (i<=j)
        {
            x=tablica[i];   //pomocnicza
            tablica[i]=tablica[j];
            tablica[j]=x;
            i++; j--;
        }
    } while(i<=j);

    if(j>prawy) quick_sort(tablica,lewy,j);
    if(i<prawy) quick_sort(tablica,i,prawy);
}

int main()
{
    cout << "Potownanie czasow sortowania v.1" << endl;
    cout << "Ile losowych liczb w tablicy?" << endl;
    cin>>ile;


    //dynamiczna alokacja tablicy
    int *tablica;
    tablica=new int[ile];

    int *tablica2;
    tablica2=new int[ile];

    //inicjowanie generatora
    srand(time(NULL));

    //wczytywanie losowych liczb do tablicy

    for (int i=0; i<ile; i++)
    {
        tablica[i] = rand()%100000+1;
    }

    //duplikat tablica do tablica2
    for (int i=0; i<ile; i++)
    {
        tablica2[i]=tablica[i];
    }

    cout<<"Sortuje teraz babelkowo, prosze czekac!" <<endl;
    start = clock();
    sortowanie_babelkowe(tablica,ile);
    stop = clock();
    czas = (double)(stop-start) / CLOCKS_PER_SEC;

    cout<<endl<<"Czas sortowania babelkowego: "<<czas<<" s"<<endl<<endl;

    cout<<"Sortuje teraz quicksort, prosze czekac!" <<endl;
    start = clock();
    quick_sort(tablica2,0, ile-1);
    stop = clock();
    czas = (double)(stop-start) / CLOCKS_PER_SEC;

    cout<<endl<<"Czas sortowania quicksort: "<<czas<<" s"<<endl;


    delete [] tablica;
    delete [] tablica2;
    return 0;
}