#include <iostream>

using namespace std;


template <class T> class c_klasa {

        public:
            T tab[100];

            template <typename M> M fill_table(M zm){

              for(M i = 0; i < zm;i++){

                    cout<<"podaj element"<<endl;

                    cin>>tab[i];
                }

            };

            template <typename M> M sort_bub(M zm) {
                cout<<"bubble sort"<<endl;
                M tmp;
                M zmm = zm-1;
                M zamiana;
                    while (true) // petla nieskonczona - wyjscie breakem
                    {
                    zamiana=false;
                    for (M i=0;i<zmm;i++) // sprawdzamy tablice od poczatku
                    {
                    if (tab[i]>tab[i+1]) // jezeli poprzedni element jest wiekszy to zamien
                    {
                    zamiana=true; // sygnalizujemy zmiane
                    tmp=tab[i];
                    tab[i]=tab[i+1];
                    tab[i+1]=tmp;
                    }
                    }
                    if (!zamiana) // jezeli nie bylo zmian to koniec sortowania - wyjscie z petli while
                    break;
                    }

            for(int i = 0; i < zm;i++)cout<<tab[i]<<" ";
            cout<<endl;

            };

            template <typename M> M sort_insert(M zm) {
                cout<<"insetrion sort"<<endl;

                    M tmp ,i ,j;

                    for (i = 1; i < zm; i++)
                    {
                    tmp = tab[i];
                    for (j = i-1; j >= 0; j--)
                    {
                    if (tmp < tab[j])
                    tab[j+1] = tab[j];
                    else
                    break;
                    }
                    tab[j+1] = tmp;
                    }



                for(int i = 0; i < zm;i++)  cout<<tab[i]<<" ";
                 cout<<endl;
            };

           template <typename M> M sort_q(M p, M r) // dzielimy tablice na dwie czesci, w pierwszej wszystkie liczby sa mniejsze badz rowne x, w drugiej wieksze lub rowne od x
                    {
                    M x = tab[p]; // obieramy x
                    M i = p, j = r, w; // i, j - indeksy w tabeli
                    while (true) // petla nieskonczona - wychodzimy z niej tylko przez return j
                    {
                    while (tab[j] > x) // dopoki elementy sa wieksze od x
                    j--;
                    while (tab[i] < x) // dopoki elementy sa mniejsze od x
                    i++;
                    if (i < j) // zamieniamy miejscami gdy i < j
                    {
                    w = tab[i];
                    tab[i] = tab[j];
                    tab[j] = w;
                    i++;
                    j--;
                    }
                    else // gdy i >= j zwracamy j jako punkt podzialu tablicy
                    return j;
                    }
                    };

             template <typename M> M sort_quick(M x,M zm) {

                M tmp = zm+1;
                M q;
                    if (x < zm)
                    {
                    q = sort_q(x,zm); // dzielimy tablice na dwie czesci; q oznacza punkt podzialu
                    sort_quick(x, q); // wywolujemy rekurencyjnie quicksort dla pierwszej czesci tablicy
                    sort_quick(q+1, zm); // wywolujemy rekurencyjnie quicksort dla drugiej czesci tablicy
                    }
                    else
                    { cout<<"quick sort"<<endl;
                        for(int k = 0; k < tmp;k++)  cout<<tab[k]<<" ";
                        cout<<endl;
                    }




            };

};


int main()
{
    cout<<"SORTOWANIE"<<endl;
    int c = 5,e;
    while(c){

    cout<<"podaj interesujacy cie typ danych"<<endl;

    cout<<"[1] int "<<endl;
    //cout<<"[2] string "<<endl;
    cout<<"[3] double "<<endl;
    cout<<"[4] char "<<endl;
    cout<<"[0] wyjdz"<<endl;

    cin>>c;

       switch(c){

       case 1:
       c_klasa<int> kochamtrap;

       cout<<"podaj ilosc liczb"<<endl;

       cin>>e;

       kochamtrap.fill_table(e);
       kochamtrap.sort_bub(e);
       kochamtrap.sort_insert(e);
       kochamtrap.sort_quick(0,e-1);
       break;

       case 3:
       c_klasa<double> kochamtrap1;

       cout<<"podaj ilosc liczb"<<endl;

       cin>>e;

       kochamtrap1.fill_table(e);
       kochamtrap1.sort_bub(e);
       kochamtrap1.sort_insert(e);
       //kochamtrap1.sort_quick(0,e-1);
       break;

       /*case 2:
        c_klasa<string> kochamtrap2;

       cout<<"podaj ilosc liczb"<<endl;

       cin>>e;

       kochamtrap2.fill_table(e);
       kochamtrap2.sort_bub(e);
       kochamtrap2.sort_insert(e);
       kochamtrap2.sort_quick(0,e-1);
       break;

*/
       }

    }

    return 0;
}