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

using namespace std;
inline void swap(int &a, int &b) {
       int t ;
       t=a;
       a=b;
       b=t;
       }

int wybieranie(int tab[], int rozmiar, long int &porownan, long int &zamiany, int odwrot){
     int temp;
     int max, mediana;
for(int i=1;i<rozmiar;i++) {
        max=i;
     for(int j=i+1;j<rozmiar;j++) {
         
         if(odwrot==1) {if(tab[max]>tab[j]) max=j;}
         else {if(tab[max]>tab[j]) max=j;}
         porownan++;
         
         }
if(max!=i) {swap(tab[i],tab[max]); zamiany++;} ;
if(i == (rozmiar / 2)) mediana=tab[i];       
};
return mediana ;
};
int wstawianie(int a[], int rozmiar, long int &porownan, long int &zamiany, int odwrot) {
     
int t, j , mediana;

for(int i = 1; i < rozmiar - 1; i++)
  {
    t = i;
    for (j = i + 1; j < rozmiar; j++){
      if(odwrot==1) {if (a[j] > a[t]) {t = j;}}
else {      if (a[j] < a[t]) {t = j;}}
     porownan++; 
      }
    swap(a[t],a[i]); zamiany++;
    if(i == (rozmiar / 2)) mediana = a[i] ;
  }     
return mediana ;
}

int babelki(int a[], int rozmiar, long int &porownan, long int &zamiany, int odwrot) {
     int temp, mediana ;
     for(int i=1;i<rozmiar;i++)
     {
             for(int j=i+1;j<rozmiar;j++) {
                     if(odwrot==1) {if(a[i] < a[j]) {swap(a[i],a[j]); zamiany++;};}
                     else {if(a[i]> a[j]) {swap(a[i],a[j]); zamiany++;};}
                     porownan++;
             }
         if(i == (mediana / 2)) mediana = a[i] ;
     }
     
     return mediana ;
     };
     
 void quicksort(int a[], int lewe, int prawe, long int &porownan, long int &zamiany, int odwrot, int rozmiar) {
    int mediana ;
    if(lewe < prawe ) {
        
       int m=lewe ;
        for(int i=lewe+1;i<=prawe;i++)
                {
                  if(a[i]<a[lewe])
                   {            
                    swap(a[++m],a[i]);
                    zamiany++;
                   }
                porownan++;
                }
        swap(a[lewe],a[m]);
        if(m == (rozmiar / 2)) cout << "\nMediana:" << a[m] << endl ;

        zamiany++;
        quicksort(a,lewe,m-1,porownan,zamiany,odwrot,rozmiar);
        quicksort(a,m+1,prawe,porownan,zamiany,odwrot,rozmiar);
    }

} ;
       
     

int kopcowanie(int d[], int N, long int &porownan, long int &zamiany, int odwrot) {
int i, j,m,k,x, mediana;     

 for(i = 2; i <= N; i++)
  {
    j = i; k = j / 2;
    x = d[i];
    while((k > 0) && (d[k] < x))
    {
      porownan++;
      d[j] = d[k];
      j = k; k = j / 2;
    }
    d[j] = x;
    zamiany++;
  }

// Rozbieramy kopiec

  for(i = N; i > 0; i--)
  {
    swap(d[1], d[i]);
    j = 1; k = 2;
    while(k < i)
    {
      porownan+=2;
      if((k + 1 < i) && (d[k + 1] > d[k]))
        {m = k + 1;}
      else
        m = k;
      if(d[m] <= d[j]) break;
      swap(d[j], d[m]); zamiany++;
      j = m; k = j + j;
    }

    if(i == (N / 2) ) mediana = d[i] ;
  }

  
 return mediana ;    
}
void wypisz(int t[],int rozmiar) {
     
// system("cls");    
 cout << "\n\n\n\tTablica:\n\t\t" ;    
 for(int i=1;i<rozmiar;i++) cout << t[i] << ", " ;
 cout << "\n" <<endl ;    

};     
void kopiuj(int a[],int b[],int rozmiar) { //pierwsza do drugiej
     for(int i=0;i<rozmiar;i++)
             b[i]=a[i];
};
long double getTime() {
  LARGE_INTEGER pc, freq;
  pc.QuadPart = 0;
  freq.QuadPart = 0;
  QueryPerformanceCounter(&pc);
  QueryPerformanceFrequency(&freq);
  if(freq.QuadPart == 0)
     return -1;
  return (long double)pc.QuadPart/(long double)freq.QuadPart;
} ;
void generuj(int t[],int rozmiar) {
     for(int i=1;i<rozmiar;i++) t[i]=(int) rand() % 20 +1;
     }     
int main()
{  
   srand((unsigned)time(NULL));
   int rozmiar = 20;
   int tablica[rozmiar];
   int pamiec[rozmiar];
   int dd;
   int mediana ;
 long     int licznik ;
     long double czas1 , czas2 ;     
     long double roznica ;
 long  int zamian ;
   int kolej=0;
   generuj(tablica,rozmiar); 
  // wypisz(tablica,rozmiar);
   do { 
        system ("cls");
   cout << "\tMenu:" << endl;
   cout << "\t\t1 - losuj tablice" << endl;
   cout << "\t\t2 - wypisz tablice" << endl;
   cout << "\t\t3 - sortowanie przez wstawianie" << endl;
   cout << "\t\t4 - sortowanie przez wybor" << endl;
   cout << "\t\t5 - sortowanie babelkowe" << endl;
   cout << "\t\t6 - sortowanie przez kopcowanie" << endl;
   cout << "\t\t7 - sortowanie metoda Quick sort" << endl;
   cout << "\t\t8 - zapamietaj tablice" << endl;
   cout << "\t\t11 - zamien kierunek sortowania" << endl;
   cout << "\t\t9 - przywroc zapamietana"  << endl;
   cin >> dd ;

   switch(dd) {
          case 1:
               generuj(tablica,rozmiar);
               break;
          case 2:
               system("cls");
               wypisz(tablica,rozmiar);
               system("Pause"); 
               break;
        case 3:
               system("cls");    
               licznik = 0;
               zamian = 0 ;
               cout << "Przed: ";wypisz(tablica,rozmiar);
               czas1=getTime() ;  // za czas1 zostanie wstawiony czas w milisekundach od momentu wlaczenia programu
// tutaj wstawic algorytm

               mediana=wstawianie(tablica,rozmiar,  licznik, zamian, kolej);
          
               czas2=getTime() - czas1;
               
               cout << "Po: ";wypisz(tablica,rozmiar);
               cout << "licznik porownan: " << licznik << ", zamian: " << zamian << ", czas: " << czas2 << ", mediana: " << mediana <<endl ; 
               system("Pause"); 
               break;
          case 4:
               system("cls");    
               licznik = 0;
               zamian = 0 ;
               cout << "Przed: ";wypisz(tablica,rozmiar);
               czas1=getTime() ;
               mediana=wybieranie(tablica,rozmiar, licznik, zamian, kolej);
               czas2=getTime() - czas1;
               
               cout << "Po: ";wypisz(tablica,rozmiar);
               cout << "licznik porownan: " << licznik << ", zamian: " << zamian << ", czas: " << czas2 << " mediana: " <<  mediana << endl ; 

               system("Pause");    
               break;
          case 5:
               system("cls");    
               cout << "Przed: ";wypisz(tablica,rozmiar);
               licznik = 0;
               zamian = 0 ;
               czas1=getTime() ;
               mediana=babelki(tablica,rozmiar, licznik, zamian, kolej);
               czas2=getTime() - czas1;
               
              roznica=czas2-czas1;
                 cout << "Po: ";wypisz(tablica,rozmiar);
               cout << "licznik porownan: " << licznik << ", zamian: " << zamian << ", czas: " << czas2 << ", mediana: "<< mediana <<endl ; 

               system("Pause"); 
               break;
          case 6:
               system("cls");    
               cout << "Przed: ";wypisz(tablica,rozmiar);
               licznik = 0;
               zamian = 0 ;
               czas1=getTime() ;
               mediana=kopcowanie(tablica,rozmiar-1, licznik, zamian, kolej);
               czas2=getTime() - czas1;
               
          
                cout << "Po: ";wypisz(tablica,rozmiar);
               cout << "licznik porownan: " << licznik << ", zamian: " << zamian << ", czas: " << czas2 << ", mediana: " << mediana << endl ; 

               system("Pause"); 
               break;
          case 7:
               system("cls");    
               cout << "Przed: ";wypisz(tablica,rozmiar);
               licznik = 0;
               zamian = 0 ;
                czas1=getTime(); //=getTime() ;
               quicksort(tablica,1,rozmiar, licznik, zamian, kolej,rozmiar);
                czas2=getTime() ; //=getTime() - czas1;
               
               roznica = czas2 - czas1;
               cout << "Po: ";wypisz(tablica,rozmiar);
               cout << "licznik porownan: " << licznik << ", zamian: " << zamian << ", czas: " << roznica << endl ; 

               system("Pause"); 
               break;
          case 8:
               kopiuj(tablica,pamiec,rozmiar);
               cout << "Skopiowane"; 
               system("Pause"); 
               break ;
          case 11:
               kolej=abs(kolej-1);
               break;
          case 9:
               kopiuj(pamiec,tablica,rozmiar);
               cout << "przywrocone" << endl; 
               system("Pause"); 
               break;
          default:
                  break;
   }
   
   }
   while(dd!=0);
    

  

    
 return 0 ;   
}