#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

int array_with_ints[] = { 1,15,231,2321,655,898,56,3,4,9 };
char array_with_characters[] = { 'p','K','v','#','b','j','C','A','k','>' };
string array_with_strings[] = { "Ala","Ma","Kota","Zatem","Kot","Ma","Ale","Nie","Wiem","Nic" };

template <typename pattern>
void bubble_sort(pattern *array,int size)
{
	for (int i = 1; i<size; ++i)
		for (int j = size - 1; j>0; --j)
		{
			if (array[j]>array[j - 1])
			{
				pattern tmp = array[j - 1];
				array[j - 1] = array[j];
				array[j] = tmp;
			}
		}
}

template <typename pattern>
void insert_sort(pattern *array,int size)
{
    pattern pom;
	int j;
	for (int i = 1; i < size; i++)
	{
		pom = array[i];
		j = i - 1;
		while (j >= 0 && array[j]>pom)
		{
			array[j + 1] = array[j];
			--j;
		}
		array[j + 1] = pom;
	}
}

template <typename pattern>
void quicksort(pattern *array, int left, int right)
{
	pattern v = array[(left + right) / 2];
	int i, j;
	pattern x;
	i = left;
	j = right;
	do
	{
		while (array[i]<v) i++;
		while (array[j]>v) j--;
		if (i <= j)
		{
			x = array[i];
			array[i] = array[j];
			array[j] = x;
			i++;
			j--;
		}
	} while (i <= j);
	if (j>left) quicksort(array, left, j);
	if (i<right) quicksort(array, i, right);
}

int read()
{
    int check;
	for (;;)
	{
		cin >> check;
		if (cin.fail())
		{
			cout << "Nie podano liczby!" << endl;
			cin.clear();
			cin.ignore();
		}
		else
			break;
	}
	return check;
}

void sort_menu()
{
	cout << "\tWYBIERZ ALGORYTM SORTOWANIA" << endl;
	cout << "[1] Sortowanie babelkowe" << endl;
	cout << "[2] Sortowanie przez wstawianie" << endl;
	cout << "[3] Sortowanie quicksort" << endl;
	cout << "[0] Wyjscie" << endl;

}

void type_menu()
{
	cout << "\tWYBIERZ TYP DANYCH" << endl;
	cout << "[1] INT" << endl;
	cout << "[2] CHAR" << endl;
	cout << "[3] STRING" << endl;
}

template <typename pattern>
void copy(pattern *array, pattern *buffor_array)
{
	for (int i = 0; i < 10; i++)
		buffor_array[i] = array[i];
}
template <typename pattern>
void print(pattern *array)
{
	for (int i = 0; i<10; i++)
	{
		cout << array[i] << " ";
	}
	cout << "\n";
}

void menu(int choice, int check)
{
    if(check == 1)
    {
        cout << "Tablica przed sortowaniem: " << endl;
        print(array_with_ints);
        cout << endl;
        int buffor_array_with_ints[10]={0};
        copy(array_with_ints, buffor_array_with_ints);
        cout << endl;
        if (choice == 1)
        {
            bubble_sort(buffor_array_with_ints, 10);
        }
        if (choice == 2)
        {
            insert_sort(buffor_array_with_ints, 10);
        }
        if (choice == 3)
        {
            quicksort(buffor_array_with_ints,0,9);
        }
        cout << "Tablica po sortowaniu: " << endl;
        print(buffor_array_with_ints);

    }
        if(check == 2)
    {
        cout << "Tablica przed sortowaniem: " << endl;
        print(array_with_characters);
        cout << endl;
        char buffor_array_with_characters[10]={0};
        copy(array_with_characters, buffor_array_with_characters);
        cout << endl;
        if (choice == 1)
        {
            bubble_sort(buffor_array_with_characters, 10);
        }
        if (choice == 2)
        {
            insert_sort(buffor_array_with_characters, 10);
        }
        if (choice == 3)
        {
            quicksort(buffor_array_with_characters,0,9);
        }
        cout << "Tablica po sortowaniu: " << endl;
        print(buffor_array_with_characters);

    }
        if(check == 3)
    {
        cout << "Tablica przed sortowaniem: " << endl;
        print(array_with_strings);
        cout << endl;
        string buffor_array_with_strings[10]={ " " };
        copy(array_with_strings,buffor_array_with_strings);
        cout << endl;
        if (choice == 1)
        {
            bubble_sort(buffor_array_with_strings, 10);
        }
        if (choice == 2)
        {
            insert_sort(buffor_array_with_strings, 10);
        }
        if (choice == 3)
        {
            quicksort(buffor_array_with_strings,0,9);
        }
        cout << "Tablica po sortowaniu: " << endl;
        print(buffor_array_with_strings);

    }
    else if(check>3||check<1)
        cout << "Nie ma takiej opcji" << endl;

}

int main()
{
    while(1)
    {
        int choice,check;
        sort_menu();
        choice = read();
        switch(choice)
        {
            case 1:
                type_menu();
                check = read();
                menu(choice,check);
                break;
            case 2:
                type_menu();
                check = read();
                menu(choice,check);
			break;
            case 3:
                type_menu();
                check = read();
                menu(choice,check);
                break;
            case 0:
                exit(0);
            default:
                cout << "Bledny wybor." << endl;
                break;

	}}
	return 0;
}