#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;

void hs();
void shs();
void is(int [],  int);
void ss();
void qs_prawy(int, int);
void qs_los(int, int);
void losuj_r();
void losuj_m();
void losuj_l();
void losuj_s();
void losuj_a();
void wyswietl(int [], int);
void powrot();
void menu();

int *tab,*tabqs;
int n = 0;

int main()
{

	cout << "podaj ilosc liczb do losowania" << endl;
	cin >> n;
	tab = new int[n];
	menu();
	getchar();

	return 0;
}

void wyswietl(int r[], int nn)
{
	cout <<endl<< " przed:" << endl;
	for (int i = 0; i <= nn-1; i++)
		cout << tab[i] << " ";
	cout << endl<<" po:" << endl;
	for (int i = 0; i <= nn-1; i++)
		cout << r[i] << " ";

	}

void losuj_r()
{
	srand(time(NULL));
	int i = 0, gg;
	bool jest = true;//tablica rosnaca
	while (jest)
	{
		tab[i] = i;
		i++;
		if (i == n)
			jest = false;

	}
	powrot();
}
void losuj_m()
{
	srand(time(NULL));
	int i = n, gg;
	bool jest = true;//tablica malejaca


	while (jest)
	{


		tab[i] = i;
		i--;
		if (i == 0)
			jest = false;

	}
	powrot();
}
void losuj_s()
{
	srand(time(NULL));
	int i = 0, gg;
	bool jest = true;//tablica stala

	gg = rand() % 100 + 1;
	while (jest)
	{
		tab[i] = gg;
		i++;
		if (i == n)
			jest = false;

	}
	powrot();
}
void losuj_l()
{
	srand(time(NULL));
	int i = 0, gg;
	bool jest = true;//tablica losowa

	while (jest)
	{
		tab[i] = rand() % 100 + 1;
		i++;
		if (i == n)
			jest = false;

	}
	powrot();
}
void losuj_a()
{
	srand(time(NULL));
	int i = 0, gg;
	bool jest = true;//tablica a



	while (jest)
	{

		if ( i < n / 2)
		{
			tab[i] = i;
			i++;
		}
		if (i == n / 2)
			gg = i;

		if (i >= n / 2)
		{
			tab[i] =gg;
			gg--;
			i++;
		}

		if (i == n)
			jest = false;

	}
	powrot();
}
void ss()
{
	int m;
	clock_t at, bt;
	int *tabb = new int[n];
	for (int i = 0; i <= n; i++)
		tabb[i] = tab[i];

	at = clock();
	for (int i = 0; i < n - 1; i++)
	{
		m = i;
		for (int j = i + 1; j < n; j++)
		{
			if (tabb[j] < tabb[m])
				m = j;
			swap(tabb[m], tabb[i]);
		}
	}
	bt = clock();
//	wyswietl(tabb, n);
	cout << endl << "czas:" << ((long float)(bt - at)) / CLOCKS_PER_SEC;
	delete tabb;
	powrot();

}
void shs()
{
	int h,temp,z;
	int *tabb = new int[n];
	clock_t at, bt;

	for (int i = 1; i <= n; i++)
		tabb[i] = tab[i -1];

	at = clock();
	for (h = 1; h < n; h = 3 * h + 1);//ten smieszny wspolczynnik
	h /= 9;

	while (h)
	{
		for (int i = n - h - 1; i >= 0; i--)
		{
			temp = tabb[i];
			z = i + h;
			while ((z < n) && (temp > tabb[z]))
			{
				tabb[z - h] = tabb[z];
				z += h;
			}
			tabb[z - h] = temp;
		}
		h /= 3;
	}
	bt = clock();
//	cout << endl << " przed:" << endl;
//	for (int i = 0; i <= n - 1; i++)
//		cout << tab[i] << " ";
//	cout << endl << " po:" << endl;
//	for (int i = 1; i <= n; i++)
//		cout << tabb[i] << " ";

	cout << endl << "czas:" << ((long float)(bt - at)) / CLOCKS_PER_SEC;
	delete tabb;
	powrot();
}
void is(int r[],int nn)//insertion sort sortowanie przez wstawianie
{
	int j,temp;
	clock_t at,bt;
	int *tabb=new int[n];

	for (int i = 0; i <= n; i++)
		tabb[i] = tab[i];
	at = clock();
	for (int i = 0; i < nn; i++)
	{
		temp = tabb[i];
		for (j = i - 1; j >= 0 && tabb[j]>temp; j--)
			tabb[j + 1] = tabb[j];
		tabb[j + 1] = temp;

	}
	bt = clock();

	//wyswietl(tabb, n);
	cout << endl << "czas:" << ((long float)(bt-at)) / CLOCKS_PER_SEC;
	getchar();
	delete tabb;
	powrot();
}
void hs()
{
		int r, d, temp,zam;

		int *tabb = new int[n];
		clock_t at, bt;

		for (int i = 1; i <= n; i++)
			tabb[i] = tab[i-1];

		at = clock();
		for (int i = n; i >=2; i--) //ukladanie kupki, od dolu
		{
			d = i;//dziecko nizej niz rodzic
			r = d / 2;//rodzic nad dzieckiem
			temp = tabb[i];
			while (temp > tabb[r] && r > 0) //tu srawdazamy czy to co mamy w tempie jest wieksze do tego co nad nim
			{
				swap(tabb[d], tabb[r]);
				d = r;
				r = d / 2;	// te w linikjki przechodza w gore jesli tak w sensie do rodzica rodzica
			}
		}

		cout << endl << " po zbudowaniu kupki:" << endl;
		for (int i = 1; i <= n; i++)
			cout << tabb[i] << " ";

		for (int i = n; i >= 2; i--) //skladanie kupki,
		{
			swap(tabb[1], tabb[i]);
			r = 1;
			d = r + r;
			while (d < i)//bedzie dzilac dopoki dziecko bedzie mneijsze od i
				{

					if (tabb[r] <= tabb[d + 1])//sprawdzamy czy prawa sciezka jest wieksza
						zam = d + 1;//jak tak to d wieksze o 1 i lecimy prawa sciezka
					else
						zam = d;//jak nie to zostawiamy i lecimy lewa
					swap(tabb[r], tabb[zam]);//zamiana atm gdzie poszlismy
					r = zam;//zwiekszamy rodzica
					d = 2 * r;//i dziecko
				}
		}

		bt = clock();

		cout << endl << " przed:" << endl;
		for (int i = 0; i <= n - 1; i++)
		cout << tab[i] << " ";
		cout << endl << " po:" << endl;
	for (int i = 1; i <= n; i++)
		cout << tabb[i] << " ";
		cout << endl << "czas:" << ((long float)(bt - at)) / CLOCKS_PER_SEC;

		delete tabb;
		powrot();
}
void qs_prawy(int i, int j)
{
	int lewy = i,  prawy = j;
	/*int piwot=tabqs[prawy];
	int current = lewy;

	for (current; current < prawy; current++)
	{
		if (tabqs[current] < piwot)
		{
			swap(tabqs[current], tabqs[lewy]);
			lewy++;
		}
	}
	swap(tabqs[lewy], tabqs[prawy]);
	qs_prawy(0, lewy);
	qs_prawy(lewy+1, prawy);*/


}
void qs_los(int i, int j)
{
	srand(time(NULL));
	int lewy = i, prawy = j;
	int piwot = rand() % lewy + prawy;;
	int current = lewy;

	for (current; current <= prawy; current++)//
	{
		if (tabqs[current] < tabqs[piwot])
		{
			swap(tabqs[current], tabqs[lewy]);
			lewy++;
		}
		if (tabqs[current] > tabqs[piwot])
		{
			swap(tabqs[current], tabqs[prawy]);
			prawy--;
		}
	}

	qs_los(0, piwot);
	qs_los(piwot + 1, prawy);

}




void powrot()
{

	cout <<endl<< "wcisnij enter by wrocic do menu" << endl;
	getchar();
	getchar();
	system("cls");
	menu();
}


void menu()
{
	int menu = 0;
	system("cls");

	cout << "1. ss" << endl;
	cout << "2. hs" << endl;
	cout << "3. is" << endl;
	cout << "4. shs" << endl;
	cout << "5. qs prawy" << endl;
	cout << "6. rosnaco" << endl;
	cout << "7. malejaco" << endl;
	cout << "8. stala" << endl;
	cout << "9. losowa" << endl;
	cout << "10. a-ksztaltna" << endl;
	cout << "11. qs losowy" << endl;

	cin >> menu;

	switch (menu)
	{
		case 1: ss(); break;
		case 2: hs(); break;
		case 3: is(tab,n); break;
		case 4: shs(); break;
		case 5:
			{
				tabqs = new int[n];
				clock_t at, bt;

				for (int i = 0; i <= n; i++)
					tabqs[i] = tab[i];
				at = clock();
				qs_prawy(0, n - 1);
				bt = clock();
				wyswietl(tabqs, n);
				cout << endl << "czas:" << ((long float)(bt - at)) / CLOCKS_PER_SEC;
				powrot();

		}; break;
		case 6: losuj_r(); break;
		case 7: losuj_m(); break;
		case 8: losuj_s(); break;
		case 9: losuj_l(); break;
		case 10: losuj_a(); break;
		case 11:
		{
				  tabqs = new int[n];
				  clock_t at, bt;

				  for (int i = 0; i <= n; i++)
					  tabqs[i] = tab[i];
				  at = clock();
				  qs_prawy(0, n - 1);
				  bt = clock();
				  wyswietl(tabqs, n);
				  cout << endl << "czas:" << ((long float)(bt - at)) / CLOCKS_PER_SEC;
				  powrot();

		}; break;
	}

}