#include <iostream>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <fstream>

using namespace std;

int fp(int x, int y)
{
    return (x<=y);
}

void sort_shell(int *tablica, int ilosc, fstream &plik1)
{
    int licznik=0;
    int h;
    int i;
    int temp;
    int c=1;
    double czas;
    const clock_t begin_time = clock();
    for (h=1; h<=ilosc/9; h=ilosc/pow(2,h));
    c++;

    for(; h>0; h /= 3)
    {
        for (i=h; i<ilosc; i++)
        {
            int j;
            temp = tablica[i];
            for (j = i-h ; j>=0; j -=h)
            {
                if (temp <=tablica[j])
                {
                    tablica[j+h] = tablica[j];
                    licznik++;
                }
                else
                    break;
            }
            tablica[j+h] = temp;
        }
    }


    /*cout << "\nPo sortowaniu Shellem." << endl;
    for(i=0; i<ilosc; i++)
    {
        cout << tablica[i] << "\t";
    }*/

    cout.precision(30);
    czas = double( clock () - begin_time ) /  CLOCKS_PER_SEC;
    plik1 << fixed << czas << endl; //jesli liczbe zamian to licznik

    //cout << "\nIlosc operacji :" << licznik << "\n";
}

void sort_hibbard(int x[], int n, fstream &plik2)
{
    int i, j,k, increment, temp,licznik=0;
    long swp=0, comp=0;
    int val;
    double czas;
    const clock_t begin_time = clock();
    val=log(n+1)/log(2);
    increment =pow(2,val)-1;
    while (increment > 0)
    {
        for (i=0; i<increment; i++)
        {
            for(j=0; j<n; j+=increment)
            {
                temp=x[j];
                for(k=j-increment; k>=0&&temp<x[k]; k-=increment)
                {
                    comp++;
                    swp++;
                    x[k+increment]=x[k];
                    licznik++;
                }
                x[k+increment]=temp;
                swp++;
                licznik++;
            }
        }
        comp++;
        val--;
        if(increment!=1)
            increment=pow(2,val)-1;
        else
            increment = 0;
    }
    /*cout << "\nPo sortowaniu Hibbardem." << endl;
    for(i=0; i<n; i++)
    {
        cout << x[i] << "\t";
    }*/
    cout.precision(30);
    czas = double( clock () - begin_time ) /  CLOCKS_PER_SEC;
    plik2 << fixed << czas << endl;


    //cout << "\nIlosc operacji :" << licznik << "\n";
}


void sort_sedgewick(int *tablica, int ilosc, fstream &plik3)
{
    int h = 0, i, g, t, j;
    int c = 1;
    int licznik = 0;
    int temp;
    double czas;
    const clock_t begin_time = clock();
    vector <int> tmp;
    tmp.push_back(h);
    do
    {
        h = (pow(4,c) + (3 * pow(2,c-1)) + 1); // funkcja z wikipedi O(N^4/3)
        tmp.push_back(h);
        if(h < ilosc) c++;
    }while(h < ilosc);
    for(g=ilosc/c;g>0;g/=c)
    {
        for(i=ilosc-g-1;i>=0;i--)
        {
            t = tablica[i];
            for(j=i+g;(j<ilosc)&&!fp(t,tablica[j]);j+=g)
            {
                tablica[j-g] = tablica[j];
                licznik++;
            }
            tablica[j-g] = t;
            licznik++;
        }
    }
    /*cout << "\nPo sortowaniu SEDGEWICKiem." << endl;
    for(i=0;i<ilosc;i++)
    {
        cout << tablica[i] << "\t";
    }*/
    cout.precision(30);
    czas = double( clock () - begin_time ) /  CLOCKS_PER_SEC;
    plik3 << fixed << czas << endl;


    //cout << "\nIlosc operacji :" << licznik << "\n";
}

/*void sort_pratt(int *pratt, int n)
{
    int i, last2ind = 0, last3ind = 0;
    printf("Po sortowaniu: \n");
    pratt[0] = 1;
    for (i=1; i < n; ++i)
    {
        if (pratt[last2ind]*2 < pratt[last3ind]*3)
        {
            pratt[i] = pratt[last2ind]*2;
            last2ind++;
        }
        else if (pratt[last2ind]*2 > pratt[last3ind]*3)
        {
            pratt[i] = pratt[last3ind]*3;
            last3ind++;
        }
        else
        {

            pratt[i] = pratt[last2ind]*2;
            last2ind++;
            last3ind++;
        }

        printf("%d \t",pratt[i]);
    }
    printf("\n");

}
*/

int main()
{
    int i, n;
    fstream plik1;
    fstream plik2;
    fstream plik3;
    fstream plik4;
    //cout << "Podaj rozmiar tablicy (W tablicy znajda sie liczby od 1 do 100): ";
    //cin >> n;

    plik1.open( "shell.txt", std::ios::in | std::ios::out );
    plik2.open( "hibbard.txt", std::ios::in | std::ios::out );
    plik3.open( "sedgewick.txt", std::ios::in | std::ios::out );
    plik4.open( "wielkoscn.txt", std::ios::in | std::ios::out );

    for(n=1000;n<=400000;n+=1000)
    {
    cout << n << "\n";
    plik4 << n << "\n";
    int zbior[n];
    int prawy = 200;
    srand(time(NULL));
    //cout << "Przed sortowaniem." << endl;
    for (int i = 0; i < n; i++)
    {
        if (i%2 == 0)
        {
            zbior[i] = rand()%prawy;
            //cout << zbior[i] << "\t";
        }
        else
        {
            zbior[i] = rand()%prawy+200;
            //cout << zbior[i] << "\t";
        }
    }
    cout << endl;



    sort_shell(zbior, n,plik1);
    sort_hibbard(zbior, n,plik2);
    sort_sedgewick(zbior, n,plik3);
    //sort_pratt(zbior,n);
    }

    plik1.close();
    plik2.close();
    plik3.close();
    plik4.close();
    return 0;
}