#include <iostream>
using namespace std;
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]) ;
       
};
};
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]);
  }     
}

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]);
             
     }
     
     
     };
     
     
void quicksort(int a[], int lewe, int prawe) {
     int lewy_start=lewe; 
     int prawy_start=prawe ;
     int piwot = a[lewe] ;
     
   while (lewe < prawe)
  {
      while ((a[prawe] >= piwot) && (lewe < prawe))
      prawe--;
    
    if (lewe != prawe)
    {
      swap(a[lewe],a[prawe]);
      lewe++;
    }
    while ((a[lewe] <= piwot) && (lewe < prawe))
      lewe++;
      
    if (lewe != prawe)
    {
        swap(a[lewe],a[prawe]);
      prawe--;
    }
}  
  a[lewe] = piwot;
  piwot = lewe;
  lewe = lewy_start;
  prawe = prawy_start;
  
  if (lewe < piwot)
    quicksort(a, lewe, piwot-1);
  if (prawe > piwot)
    quicksort(a , piwot+1, prawe);
} ;
       
     

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;
    }
  }

  
     
}
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);
               system("Pause"); 
               break;
          case 4:
               system("cls");    
               cout << "Przed: ";wypisz(tablica,rozmiar);
               wybieranie(tablica,rozmiar);
               cout << "Po: ";wypisz(tablica,rozmiar);
               system("Pause");    
               break;
          case 5:
               system("cls");    
               cout << "Przed: ";wypisz(tablica,rozmiar);
               babelki(tablica,rozmiar);
               cout << "Po: ";wypisz(tablica,rozmiar);
               system("Pause"); 
               break;
          case 6:
               system("cls");    
               cout << "Przed: ";wypisz(tablica,rozmiar);
               kopcowanie(tablica,rozmiar-1);
               cout << "Po: ";wypisz(tablica,rozmiar);
               system("Pause"); 
               break;
          case 7:
               system("cls");    
               cout << "Przed: ";wypisz(tablica,rozmiar);
               quicksort(tablica,1,rozmiar);
               cout << "Po: ";wypisz(tablica,rozmiar);
               system("Pause"); 
               break;
          case 0:
               return 0 ;
          default:
                  break;
   }
   
   }
   while(dd!=0);
    

  

    
 return 0 ;   
}