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

using namespace std;
clock_t start, stop;
double czas;

void quicksort(int *tab, int lewy, int prawy, int &zamiana, int &porownanie)
{
    int i = lewy, j = prawy, p;
    p = tab[(lewy + prawy) / 2];

    do
    {
porownanie++;
        while (tab[i] < p)
        {
            i++;
porownanie++;
        }
porownanie++;
        while (tab[j] > p)
        {
porownanie++
            j--;
        }
        porownanie++;
        if (i <= j)
        {
            swap(tab[i++], tab[j--]);
            zamiana++;
        }
    } while (i <= j);
    porownanie++;
    if (i < prawy)quicksort(tab, i, prawy, zamiana, porownanie);
    porownanie++;
    if (j > lewy)quicksort(tab, lewy, j, zamiana, porownanie);
}

void merge(int *tab, int lewy, int srodek, int prawy, int *pom, int &zamiana, int &porownanie)
{
    int i = lewy, j = srodek + 1;
    for (int i = lewy; i <= prawy; i++)
    {
        pom[i] = tab[i];
    }
    for (int k = lewy; k <= prawy; k++)
    {
        porownanie++;
        if (i <= srodek)
        {
            porownanie++;
            if (j <= prawy)
            {
                porownanie++;
                if (pom[i] > pom[j])
                {
                    tab[k] = pom[j++];
                }
                else
                    tab[k] = pom[i++];
            }
            else
                tab[k] = pom[i++];
        }
        else
            tab[k] = pom[j++];
    }

}

void mergesort(int *tab, int lewy, int prawy, int* pom, int &zamiana, int &porownanie)
{
    porownanie++;
    if (prawy <= lewy)return;

    int srodek = (lewy + prawy) / 2;

    mergesort(tab, lewy, srodek, pom, zamiana, porownanie);
    mergesort(tab, srodek + 1, prawy, pom, zamiana, porownanie);

    merge(tab, lewy, srodek, prawy, pom, zamiana, porownanie);
}

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

void wybieranie(int *tab, int n, int &zamiana, int &porownanie)
{
    int i, j, pmin, x;
    for (i = 0; i < n - 1; i++)
    {
        pmin = i;
        for (j = i + 1; j < n; j++)
        {
            porownanie++;
            if (tab[j] < tab[pmin])
                pmin = j;
        }
        zamiana++;
        x = tab[i];
        tab[i] = tab[pmin];
        tab[pmin] = x;
    }
}

void kopiec(int *tab, int n, int &zamiana, int &porownanie)
{
    int i, j, k, x, m;
    porownanie++;
    for (i = 2; i <= n; i++)
    {
        j = i; k = j / 2;
        x = tab[i];
        porownanie++;
        while ((k > 0) && (tab[k] < x))
        {
        porownanie++;
            tab[j] = tab[k];
            j = k; k = j / 2;
        }
        tab[j] = x;
        zamiana++;
    }

    //rozbieramy kopiec

    for (i = n; i > 1; i--)
    {
        x = tab[1];
        tab[1] = tab[i];
        tab[i] = x;
        zamiana++;
        j = 1; k = 2;
        while (k < i)
        {
            porownanie++;
            if ((k + 1 < i) && (tab[k + 1] > tab[k]))
                m = k + 1;
            else
                m = k;
            porownanie++;
            if (tab[m] <= tab[j])
                break;
            x = tab[j];
            tab[j] = tab[m];
            tab[m] = x;
            zamiana++;
            j = m;
            k = j + j;
        }
    }
}

void bsortopt(int *tab, int n, int &zamiana, int &porownanie)
{
    int pmin = 0, pmax = n - 1, p;
    do
    {
        p = -1;
        for (int i = pmin; i < pmax; i++)
        {
            porownanie++;
            if (tab[i] > tab[i + 1])
            {
                zamiana++;
                swap(tab[i], tab[i + 1]);
                porownanie++;
                if (p < 0) pmin = i;
                p = i;
            }
        }
        if (pmin) pmin--;
        pmax = p;
    } while (p >= 0);
}

void main()
{
    int zamiana = 0, porownanie = 0;
    srand(time(NULL));
    int ile;
    cout << "Podaj liczbe elementow: ";
    cin >> ile;
    int *tab = new int[ile];
    int *tab1 = new int[ile];
    int *tab2 = new int[ile];
    int *kop = new int[ile + 1];
    int *tab3 = new int[ile];
    int *tab4 = new int[ile];
    int *pom = new int[ile];

    //tablice random

    /*for (int i = 1; i <= ile; i++)
    {
    kop[i] = rand() % 100+1;
    tab[i - 1] = kop[i];
    tab1[i - 1] = kop[i];
    tab2[i - 1] = kop[i];
    tab3[i - 1] = kop[i];
    tab4[i - 1] = kop[i];
    }*/

    //tablice posortowane

    /*for (int i = 1; i <= ile; i++)
    {
    kop[i] = i;
    tab[i - 1] = kop[i];
    tab1[i - 1] = kop[i];
    tab2[i - 1] = kop[i];
    tab3[i - 1] = kop[i];
    tab4[i - 1] = kop[i];
    }*/

    //tablice czesciowo posortowane

    for (int i = 1; i < ile / 2; i++)
    {
        kop[i] = i;
        tab[i - 1] = kop[i];
        tab1[i - 1] = kop[i];
        tab2[i - 1] = kop[i];
        tab3[i - 1] = kop[i];
        tab4[i - 1] = kop[i];
    }

    for (int i = ile / 2; i <= ile; i++)
    {
        kop[i] = rand() % 10000 + 1050;
        tab[i - 1] = kop[i];
        tab1[i - 1] = kop[i];
        tab2[i - 1] = kop[i];
        tab3[i - 1] = kop[i];
        tab4[i - 1] = kop[i];
    }


    cout << endl << "Sortuje babelkowo. Prosze czekac!" << endl;
    start = clock();
    bsortopt(tab, ile, zamiana, porownanie);
    stop = clock();
    czas = (double)(stop - start) / CLOCKS_PER_SEC;
    cout << endl << "Czas sortowania babelkowego opt: " << czas << " s" << endl << "Ilosc porownan: " << porownanie << endl << "Ilosc zamian: " << zamiana << endl;

    zamiana = 0; porownanie = 0;

    cout << endl << "Sortuje quicksort. Prosze czekac!" << endl;
    start = clock();
    quicksort(tab1, 0, ile - 1, zamiana, porownanie);
    stop = clock();
    czas = (double)(stop - start) / CLOCKS_PER_SEC;
    cout << endl << "Czas sortowania quicksort: " << czas << " s" << endl << "Ilosc porownan: " << porownanie << endl << "Ilosc zamian: " << zamiana << endl;

    zamiana = 0; porownanie = 0;

    cout << endl << "Sortuje przez kopcowanie. Prosze czekac!" << endl;
    start = clock();
    kopiec(kop, ile, zamiana, porownanie);
    stop = clock();
    czas = (double)(stop - start) / CLOCKS_PER_SEC;
    cout << endl << "Czas sortowania przez kopcowanie: " << czas << " s" << endl << "Ilosc porownan: " << porownanie << endl << "Ilosc zamian: " << zamiana << endl;

    zamiana = 0; porownanie = 0;

    cout << endl << "Sortowanie przez wybieranie. Prosze czekac!" << endl;
    start = clock();
    wybieranie(tab2, ile, zamiana, porownanie);
    stop = clock();
    czas = (double)(stop - start) / CLOCKS_PER_SEC;
    cout << endl << "Czas sortowania przez wybieranie: " << czas << " s" << endl << "Ilosc porownan: " << porownanie << endl << "Ilosc zamian: " << zamiana << endl;

    zamiana = 0; porownanie = 0;

    cout << endl << "Sortowanie przez wstawianie. Prosze czekac!" << endl;
    start = clock();
    wstawianie(tab3, ile, zamiana, porownanie);
    stop = clock();
    czas = (double)(stop - start) / CLOCKS_PER_SEC;
    cout << endl << "Czas sortowania przez wstawianie: " << czas << " s" << endl << "Ilosc porownan: " << porownanie << endl << "Ilosc zamian: " << zamiana << endl;

    zamiana = 0; porownanie = 0;

    cout << endl << "Sortowanie przez scalanie. Prosze czekac!" << endl;
    start = clock();
    mergesort(tab4, 0, ile - 1, pom, zamiana, porownanie);
    stop = clock();
    czas = (double)(stop - start) / CLOCKS_PER_SEC;
    cout << endl << "Czas sortowania przez scalanie: " << czas << " s" << endl << "Ilosc porownan: " << porownanie << endl << "Ilosc zamian: " << zamiana << endl;

    zamiana = 0; porownanie = 0;

    delete[] tab4;
    delete[] tab3;
    delete[] kop;
    delete[] tab2;
    delete[] tab;
    delete[] tab1;
    cout << endl;
    system("PAUSE");
}