#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
#include <string>
#include <sstream>

#define N 20000
#define MAX 32768

using namespace std;

int T[N];
string start,stop;
int hason, cserel;

string itt_az_ido(string sz)
{
    time_t azIdo = time(NULL);
    struct tm *Ido = localtime(&azIdo);

    //int nap = Ido->tm_mday;
    //int honap = Ido->tm_mon + 1; // hónap 0-11 közötti számként vannak, így +1 kell
    //int ev = Ido->tm_year + 1900; // 1900 óta mennyi év telt el, ezt kapjuk alapból
    int ora=Ido->tm_hour;
    int perc=Ido->tm_min;
    int mp=Ido->tm_sec;

    string ora_s, perc_s, mp_s;

    ostringstream convert;
    convert << ora;
    ora_s=convert.str();
    ostringstream convert1;
    convert1 << perc;
    perc_s=convert1.str();
    ostringstream convert2;
    convert2 << mp;
    mp_s=convert2.str();

    string s=sz+ora_s+":"+perc_s+":"+mp_s;
    cout << s << endl;
    return s;
}

bool hasonlit(int egyik, int masik)
{
    hason++;
    if(egyik>masik) return true;
    else return false;
}

void csere(int x, int y)
{
    cserel++;
    swap(T[x],T[y]);
}

void generator()
{
    cout << "Adatgenerálás...";
    ofstream fki;
    fki.open("input.txt");

    for(int i=0;i<N;i++)
    {
        T[i]=rand()%MAX+1;
        fki << T[i] << endl;
    }
    fki.close();
    cout << "vége!" << endl;
}

void frissit()
{
    ifstream fbe;
    fbe.open("input.txt");
    for(int i=0;i<N;i++)
    {
        fbe >> T[i];
    }
    fbe.close();
}

void indit(string rendez)
{
    cout << "----------------------------------------" << endl;
    cserel=0;
    hason=0;
    cout << rendez << " rendezés..." << endl;
    cout << "----------------------------------------" << endl;
    cout << "Adatok beolvasása...";
    frissit();
    cout << "Vége!" << endl;
}

void kiir(char* fn)
{

    cout << "Hasonlítások száma: " << hason << endl;
    cout << "Mozgatások (cserék) száma: " << cserel << endl;
    cout << "Rendezett adatok kiírása (" << fn << ")...";
    ofstream fki;
    fki.open(fn);
    fki << start << endl;
    fki << stop << endl;
    fki << hason << endl;
    fki << cserel << endl;
    fki << "--------------------" << endl;
    for(int i=0;i<N;i++)
    {
        fki << T[i] << endl;
    }
    fki.close();
    cout << "...Vége!" << endl;
}

void cseres()
{
    indit("Egyszerű cserés");
    start=itt_az_ido("Kezdés:");
    for(int i=0;i<N-1;i++)
    {
        for(int j=i+1;j<N;j++)
        {
            if(hasonlit(T[i],T[j])) csere(i,j);
        }
    }
    stop=itt_az_ido("Vége:");
    kiir("cseres.txt");
}

void minimumos()
{
    indit("Minimumos");
    start=itt_az_ido("Kezdés:");
    int Min;
    for(int i=0;i<N-1;i++)
    {
        Min=i;
        for(int j=i+1;j<N;j++)
        {
            if(hasonlit(T[Min],T[j])) Min=j;
        }
        csere(Min,i);
    }
    stop=itt_az_ido("Vége:");
    kiir("minim.txt");
}

void buborekos()
{
    indit("Buborékos");
    start=itt_az_ido("Kezdés:");
    for(int i=N;i>1;i--)
    {
        for(int j=0;j<i-1;j++)
        {
            if(hasonlit(T[j],T[j+1])) csere(j,j+1);
        }
    }
    stop=itt_az_ido("Vége:");
    kiir("buborekos.txt");
}

void jav_buborekos()
{
    indit("Javított buborékos");
    start=itt_az_ido("Kezdés:");
    int i=N-1, cs;
    while(i>=1)
    {
        cs=0;
        for(int j=0;j<i;j++)
        {
            if(hasonlit(T[j],T[j+1]))
            {
                csere(j,j+1);
                cs=j;
            }
        }
        i=cs;
    }
    stop=itt_az_ido("Vége:");
    kiir("jav_buborekos.txt");
}

void beilleszteses()
{
    indit("Beillesztéses");
    start=itt_az_ido("Kezdés:");
    int j;
    for(int i=1;i<N;i++)
    {
        j=i-1;
        while(j>=0&&hasonlit(T[j],T[j+1]))
        {
            csere(j,j+1);
            j=j-1;
        }
    }
    stop=itt_az_ido("Vége:");
    kiir("beilleszteses.txt");
}

void jav_beilleszteses()
{
    indit("Javított beillesztéses");
    start=itt_az_ido("Kezdés:");
    int j, S;
    for(int i=1;i<N;i++)
    {
        j=i-1; S=T[i];
        while(j>=0&&hasonlit(T[j],S))
        {
            T[j+1]=T[j]; cserel++;
            j=j-1;
        }
        T[j+1]=S; cserel++;
    }
    stop=itt_az_ido("Vége:");
    kiir("jav_beilleszteses.txt");
}

/*
SHELL és QUICK SORT HAMAROSAN...
*/

int main()
{
    setlocale(LC_ALL, "hun");
    cout << "RENDEZÉSI ALGORITMUSOK" << endl;
    cout << "----------------------" << endl;
    cout << "Adatok száma: " << N << ", nagyságrend: " << MAX << endl;
    srand(time(NULL));
    generator();
    cseres();
    minimumos();
    buborekos();
    jav_buborekos();
    beilleszteses();
    jav_beilleszteses();
    return 0;
}