/*Miłosz Czarnota gr1 */

#include <iostream>
using namespace std;
int mediana ;
inline void swap(int &a, int &b) {
       int t ;
       t=a;
       a=b;
       b=t;
       }
 
void wybieranie(int tab[], int rozmiar){
     int temp;
     int max;
for(int i=1;i<rozmiar;i++) {
        max=i;
     for(int j=i+1;j<rozmiar;j++)
         if(tab[max]>tab[j]) max=j;
                            
if(max!=i) swap(tab[i],tab[max]) ;
if(i==(rozmiar /2)) mediana=tab[i] ;
};
};
void wstawianie(int a[], int rozmiar) {
     
int t, j ;
 
for(int i = 1; i < rozmiar - 1; i++)
  {
    t = i;
    for (j = i + 1; j < rozmiar; j++)
      if (a[j] < a[t]) t = j;
    swap(a[t],a[i]);
  if(i==(rozmiar /2)) mediana=a[i] ;
  }     
}
 
void babelki(int a[], int rozmiar) {
     int temp ;
     for(int i=1;i<rozmiar;i++)
     {
             for(int j=i+1;j<rozmiar;j++)
             if(a[i]> a[j]) swap(a[i],a[j]);
     if(i==(rozmiar /2)) mediana=a[i] ;        
     }
     
     
     };
     
     
     
 void quicksort(int a[], int lewe, int prawe, int rozmiar) {

    if(lewe < prawe ) {
        
       int m=lewe ;
        for(int i=lewe+1;i<=prawe;i++)
                {
                  if(a[i]<a[lewe])
                   {            
                    swap(a[++m],a[i]);

                   }
               
                }
        swap(a[lewe],a[m]);
        if(m == (rozmiar / 2)) mediana=a[m] ;

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

} ;
       
       
     
 
void kopcowanie(int d[], int N) {
int i, j,m,k,x;     
 
 for(i = 2; i <= N; i++)
  {
    j = i; k = j / 2;
    x = d[i];
    while((k > 0) && (d[k] < x))
    {
      d[j] = d[k];
      j = k; k = j / 2;
    }
    d[j] = x;
  }
 
// Rozbieramy kopiec
 
  for(i = N; i > 0; i--)
  {
    swap(d[1], d[i]);
    j = 1; k = 2;
    while(k < i)
    {
      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]);
      j = m; k = j + j;
      if(i == ((N / 2) +1) ) mediana = d[i] ;
    }
  }
 
  
     
}
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 generuj(int t[],int rozmiar) {
     for(int i=1;i<rozmiar;i++) t[i]=(int) rand() % 20 ;
     }     
int main()
{  
   srand((unsigned)time(NULL));
   int rozmiar = 10;
   int tablica[rozmiar];
   int dd;
   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\t0 - wyjscie" << 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");    
               cout << "Przed: ";wypisz(tablica,rozmiar);
               wstawianie(tablica,rozmiar);
              
               cout << "Po: ";wypisz(tablica,rozmiar);
               cout << "\nmediana: " << mediana << endl << endl ;
               system("Pause"); 
               break;
          case 4:
               system("cls");    
               cout << "Przed: ";wypisz(tablica,rozmiar);
               wybieranie(tablica,rozmiar);
               cout << "Po: ";wypisz(tablica,rozmiar);
                cout << "\nmediana: " << mediana << endl << endl ;
               system("Pause");    
               break;
          case 5:
               system("cls");    
               cout << "Przed: ";wypisz(tablica,rozmiar);
               babelki(tablica,rozmiar);
               cout << "Po: ";wypisz(tablica,rozmiar);
                cout << "\nmediana: " << mediana << endl << endl ;
               system("Pause"); 
               break;
          case 6:
               system("cls");    
               cout << "Przed: ";wypisz(tablica,rozmiar);
               kopcowanie(tablica,rozmiar-1);
               cout << "Po: ";wypisz(tablica,rozmiar);
                cout << "\nmediana: " << mediana << endl << endl ;
               system("Pause"); 
               break;
          case 7:
               system("cls");    
               cout << "Przed: ";wypisz(tablica,rozmiar);
               quicksort(tablica,1,rozmiar,rozmiar);
               cout << "Po: ";wypisz(tablica,rozmiar);
                cout << "\nmediana: " << mediana << endl << endl ;
               system("Pause"); 
               break;
          case 0:
               return 0 ;
          default:
                  break;
   }
   
   }
   while(dd!=0);
    
 
  
 
    
 return 0 ;   
}