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

using namespace std;
void sortowanie_babelkowe(int *, int);
void sortowanie_babelkowe_ulepszone(int* , int );
void sortowanie_Przez_Wstawianie(int* tab, int ile)
{
    DWORD t5, t6;
    t5=GetTickCount();

  for(int j = ile - 2 ; j >= 0 ; j--)
    {
        int x = tab[j];
        int i = j + 1;
        while((i < ile) && (x > tab[i]))
        {
            tab[i - 1] = tab[i];
            i++;
        }
        tab[i - 1] = x;
    }
    t6=GetTickCount() - t5;
    cout << "\nCzas trwania sortowania : " << t6 << " ms" << endl;

}
//void sortowanie_Przez_Wybieranie(int*, int);
//void sortowanie_quicksort (int*,int*,int,int);
int main()
{
    int ile;
    cout << "Ile pseudo losowych liczb w tablicy?: " << endl;
    cin >> ile;

    int *tablica;
    tablica = new int[ile];
    int *tablica2;
    tablica2 = new int[ile];
    int *tablica3;
    tablica3 = new int[ile];
    //int *tablica4;
    //tablica4 = new int[ile];

    //wylosowanie liczb i zpaisanie ich do tablicy
    srand(time(NULL)); // generator pseudo losowych liczb
    for(int i = 0 ; i < ile; i++)
    {
        tablica[i] = rand()%100+1;
    }
    //przepisanie tablicy do tablicy
    for(int i =0 ; i< ile; i++)
    {
        tablica2[i] = tablica[i];
    }
    for(int i =0 ; i< ile; i++)
    {
        tablica3[i] = tablica[i];
    }
   /* for(int i =0 ; i< ile; i++)
    {
        tablica4[i] = tablica[i];
    }*/

  for(int i = 0; i<ile; i++)
  {
      cout << tablica3[i] << endl;
  }

  for(int i = 0; i<ile ; i++)
    tablica3[i] = 0;

  for(int i = 0; i<ile; i++)
  {
      cout << i << ":" << tablica3[i] << endl;
  }


  cout << "\n\nSortowanie babelkowe  " << endl;


    sortowanie_babelkowe(tablica, ile);
    fstream bablekowe;
    bablekowe.open( "babelkowe.txt", ios::out );
    if( bablekowe.good() )
    {
        for (int i = 0; i < ile; i++)
        {
            if (i%10 != 9)
            {
                bablekowe << tablica[i] << '\t';
            }
            else
            {
                bablekowe << tablica[i] << endl;
            }
        }
        bablekowe.close();
    }

cout << "\n\nSortowanie ulepszone babelkowe  " << endl;


    sortowanie_babelkowe_ulepszone(tablica2, ile);
    fstream babelkowe_ulepszone;
    babelkowe_ulepszone.open( "babelkowe_ulepszone.txt", ios::out );
    if( babelkowe_ulepszone.good() )
    {
        for (int i = 0; i < ile; i++)
        {
            if (i%10 != 9)
            {
                babelkowe_ulepszone << tablica2[i] << '\t';
            }
            else
            {
                babelkowe_ulepszone << tablica2[i] << endl;
            }
        }
        babelkowe_ulepszone.close();
    }


cout << "\nSortowanie przez wstawianie   " << endl;


    sortowanie_Przez_Wstawianie(tablica3, ile);
    cout << "\nDEBUG";
    /*fstream wstawianie;
    wstawianie.open( "wstawianie.txt", ios::out );
    if( wstawianie.good() )
    {
        for (int i = 0; i < wielkosc; i++)
        {
            if (i%10 != 9)
            {
                wstawianie << tab3[i] << '\t';
            }
            else
            {
                wstawianie << tab3[i] << endl;
            }
        }
        wstawianie.close();
    }*/

/* cout << "\n***************************************************    " << endl;
    cout << "\nSortowanie przez wybieranie     " << endl;


    sortowanie_Przez_Wybieranie(tab4, wielkosc);

    fstream wybieranie;
    wybieranie.open( "wybieranie.txt", ios::out );
    if( wybieranie.good() )
    {
        for (int i = 0; i < wielkosc; i++)
        {
            if (i%10 != 9)
            {
                wybieranie << tab4[i] << '\t';
            }
            else
            {
                wybieranie << tab4[i] << endl;
            }
        }
         wybieranie.close();
    }*/


/*cout << "\nQuick Sort   " << endl;
    sortowanie_quicksort(tab3, wielkosc,lewy,prawy);

    fstream qsort;
    qsort.open( "qsort.txt", ios::out );
    if( qsort.good() )
    {
        for (int i = 0; i < wielkosc; i++)
        {
            if (i%10 != 9)
            {
                qsort << tab3[i] << '\t';
            }
            else
            {
                qsort << tab3[i] << endl;
            }
        }
    }
    qsort.close();
*/
cout << "\nDEBUG";
    delete [] tablica;
    cout << "\nUSUNOLEM tab1";
    delete [] tablica2;
    cout << "\nUSUNOLEM tab2";
    delete [] tablica3;
    cout << "\nUSUNOLEM tab3";
  //  delete [] tab4;
    return 0;
}


void sortowanie_babelkowe(int *tab, int wielkosc)
{
    DWORD t1, t2;
    t1=GetTickCount();
 for(int i = 1; i < wielkosc; i++)
    {
        for(int j = wielkosc - 1; j>=1; j--)
        {
            if(tab[j] < tab[j-1])
            {
                int a;
                a = tab[j-1];
                tab[j-1] = tab[j];
                tab[j] = a;
            }
        }
    }
    t2=GetTickCount() - t1;
    cout << "\nCzas trwania sortowania : " << t2 << " ms" << endl;
    cout << "\n***************************************************    " << endl;

}
void sortowanie_babelkowe_ulepszone(int* tab, int wielkosc)
{
    DWORD t3, t4;
    t3=GetTickCount();
   for(int j= wielkosc - 1; j>1; j--)
        for(int i = 0; i <= j ; i++)
            if ( tab[i] > tab[i+1] )
            {
                int pom = tab[i+1];
                tab[i+1] = tab[i];
                tab[i] = pom;
            }

    t4=GetTickCount() - t3;
    cout << "\nCzas trwania sortowania : " << t4 << " ms" << endl;
    cout << "\n***************************************************    " << endl;

}

/*void sortowanie_Przez_Wstawianie(int* tab, int ile)
{
    DWORD t5, t6;
    t5=GetTickCount();

  for(int j = ile - 2 ; j >= 0 ; j--)
    {
        int x = tab[j];
        int i = j + 1;
        while((i < ile) && (x > tab[i]))
        {
            tab[i - 1] = tab[i];
            i++;
        }
        tab[i - 1] = x;
    }
    t6=GetTickCount() - t5;
    cout << "\nCzas trwania sortowania : " << t6 << " ms" << endl;

}*/

/*void sortowanie_Przez_Wybieranie(int* tab, int wielkosc)
{
    DWORD t7, t8;
    t7=GetTickCount();

    for(int j = 0; j < wielkosc - 1; j++)
    {
        int pmin = j;
        for(int i = j + 1 ; i < wielkosc ; i++)
        {
            if(tab[i] < tab[pmin])
            {
                pmin = i;
            }
        }
        int a;
        a = tab[pmin];
        tab[pmin] = tab[j];
        tab[j] = a;
    }
    t8=GetTickCount() - t7;
    cout << "\nCzas trwania sortowania : " << t8 << " ms" << endl;
     cout << "\n***************************************************    " << endl;
}
void sortowanie_quicksort(int* tab, int wielkosc,int* lewy, int* prawy,int j,int k,int piwot)
{
    DWORD t1, t2;
    t1=GetTickCount();

  k = (lewy + prawy) / 2;
  piwot = tab[k]; tab[k] = tab[prawy];
  for(j = k = lewy; k < prawy; k++)
  if(tab[k] < piwot)
  {
    swap(tab[k], tab[k]);
    j++;
  }
  tab[prawy] = tab[j]; tab[j] = piwot;
  if(lewy < j - 1)  sortowanie_quicksort(lewy, j - 1);
  if(j + 1 < prawy) sortowanie_quicksort(j + 1, prawy);
  t2=GetTickCount() - t1;
      cout << "\nCzas trwania sortowania : " << t2 << " ms" << endl;
     cout << "\n***************************************************    " << endl;

}
*/