#include<iostream>
#include<cstdlib>
#include<time.h>

using namespace std;

template <typename T>
class Sort {
private:
	T *pom; // tablica pomocnicza potrzebna do scalania
	T *tab;
	int size;

public:
	Sort(int _size)
	{
		size = _size;
		tab = new T[size];
		pom = new T[size];
	}
	~Sort() {
		delete [] tab;
		delete[] pom;
	}
	void wyswietlanie()
	{
		for (int i = 0; i < size; i++)
			cout << tab[i] << " ";
		cout << "wyswietlono pomyslnie " << size << " elementow" << endl;
	}

	void merge_f(int lewyindex, int srodek, int prawyindex) //scalanie posortowanych tablic
	{
		int poczatek1 = lewyindex; //poczatek 1 polowy tablicy
		int poczatek2 = srodek + 1; // poczatek 2 polowy tablicy
		int pomocnik = lewyindex;	// kontrolny na jakie miejsce wpisujemy najmmniejszy element do tablicy
		//kopiujemy lewą i prawą część tablicy do tablicy pomocniczej DO YWJEBANIA CHYBA!!!!!!!!!!!!!!!!!!!!!!!!!
		for (int i = lewyindex; i <= prawyindex; i++)
			pom[i] = tab[i];

		while (poczatek1 <= srodek && poczatek2 <= prawyindex)
		{
			if (pom[poczatek1] <= pom[poczatek2])
			{
				tab[pomocnik] = pom[poczatek1];
				poczatek1++;
			}
			else
			{
				tab[pomocnik] = pom[poczatek2];
				poczatek2++;
			}
			pomocnik++;
		}
		while (poczatek1 <= srodek)
		{
			tab[pomocnik] = pom[poczatek1];
			pomocnik++;
			poczatek1++;

		}
	}

	void mergeSort(int lewyindex, int prawyindex)
	{
		//gdy mamy jeden element, to jest on już posortowany
		if (lewyindex < prawyindex)
		{

			//znajdujemy srodek podtablicy
			int srodek = (prawyindex + lewyindex) / 2;

			//dzielimy tablice na częsć lewą i prawa
			mergeSort( lewyindex, srodek);
			mergeSort(srodek + 1, prawyindex);

			merge_f(lewyindex, srodek, prawyindex);
		}
	}

	/* Sortowanie szybkie */
	void sort_szybkie(int lewyindex, int prawyindex) // ew na poczatku w nawiasie int tab[]????????????????????????
	{
		int i, j, pivot;
		i = (lewyindex + prawyindex) / 2;
		pivot = tab[i];
		tab[i] = tab[prawyindex];

		i = lewyindex;
		j = lewyindex;
		while (i < prawyindex) {
			if (tab[i] < pivot) {
				int tmp = tab[i];
				tab[i] = tab[j];
				tab[j] = tmp;
				j++;
			}
			i++;
		}
		tab[prawyindex] = tab[j];
		tab[j] = pivot;
		if (lewyindex < j - 1) {
			sort_szybkie(lewyindex, j - 1);
		}
		if (j + 1 < prawyindex) {
			sort_szybkie(j + 1, prawyindex);
		}
	}
	/* Sortowanie introspektywne*/

	void intro(int lewyindex, int prawyindex, int max_wyw) {
		int i, j;
		int pivot;
		//max wyw moment aby zatrzymac quicksorta&& po zatrzymaniu robi wstawianie albo inne sortowanie - intro sort to ulepszenie quicksorta o taka mozliwosc

		if (max_wyw == 0) {
			insert_sort();
		}

		if (max_wyw > 0) {
			max_wyw = max_wyw - 1;

			i = (lewyindex + prawyindex) / 2;
			pivot = tab[i];
			tab[i] = tab[prawyindex];

			i = lewyindex;
			j = lewyindex;
			while (i < prawyindex) {
				if (tab[i] < pivot) {
					int tmp = tab[i];
					tab[i] = tab[j];
					tab[j] = tmp;
					j++;
				}
				i++;
			}
			tab[prawyindex] = tab[j];
			tab[j] = pivot;
			if (lewyindex < j - 1) {
				intro(lewyindex, j - 1, max_wyw);
			}
			if (j + 1 < prawyindex) {
				intro(j + 1, prawyindex, max_wyw);
			}
		}

	}
	void sort_intro(int lewyindex, int prawyindex) {
		int max_wyw = int(2 * log(prawyindex - lewyindex + 1));
	}


		void insert_sort() //DZIAAAAALA
		{
			for (int j = 0; j <size; j++)
				for (int i = 0; i <size; i++)
				{
					if (tab[i - 1] > tab[i])
					{// patrze czy moj prio jest wiekszy od wczesniejeszego
					 //jesli tak to przesuwamy wszytsko w prawo i wstawiamy nasz elem i klucz


						T temp_v = tab[i - 1]; //przechowuja nastepny klucz


						tab[i - 1] = tab[i];
						tab[i] = temp_v;
						//moving values and keys 1 position to the right
						//break;
					}
				}
		}
		void uzupelnianie(T dlugosc) {
			srand(time(NULL));
			for (int i = 0; i < dlugosc; i++)
				tab[i] = rand();
		}

		void odwracanie_tab()
		{

			double temp;
			for (int i = 0; i < size / 2; i++)
			{
				temp = tab[size - i - 1];
				tab[size- i - 1] = tab[i];
				tab[i] = temp;
			}
		}

};



int main()
{
	double time;
	long int n=0; //liczba elem

		cout << "Wpisz ilosc elementow w tablicy...\n mozliwe opcje to: \n 10 000 elementow \n  50 000 elementow \n 100 000 elementow\n  500 000 elementow\n  1 000 000 elementow\n";
		cin >> n;
		Sort <double> m(n);
		m.uzupelnianie(n);
		cout << endl << endl;
		//m.wyswietlanie();
		//cout << endl;
		//m.wyswietlanie();

		double time_begin = clock();
		for (int i = 0; i < 100; i++)
		{
			m.sort_szybkie(0,n-1); //tu zmienia sie sposob sortowania
		}
		double time_end = clock();
		time = (time_end - time_begin) / 100;
	cout << endl << "Czas  sort'a: " << time<< endl;
	//m.wyswietlanie();
	cout << endl;

	system("pause");
	return 0;
}
/*
//ponizej sortowanie gdy 50% jest juz posortowane

m.sort_intro(0, n/2 - 1); //tu zmienia sie sposob sortowania
double time_begin = clock();

for (int i = 0; i < 100; i++) //50% posortowane na poczatku reszta rand()
{
	m.sort_intro(0, n - 1); //tu zmienia sie sposob sortowania
}
double time_end = clock();
time = (time_end - time_begin) / 100;

//posortowane ale odwrotnie

*/