#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <chrono>
#include <fstream>
using namespace std;



void selectionSort(vector<int> &wektor, int n)  //nie bede sie rozwodzil nad dzialaniem algorytmow sortujacych bo to by zajelo 30 minut a to wiedza dostepna w sekunde w google
{
	int vecsize = wektor.size(); //wielkosc vectora
	for (int j = 0; j < vecsize - 1; ++j) {

		int min = j;
		for (int i = j + 1; i < vecsize; ++i) {
			if (wektor.at(min) > wektor.at(i)) {
				min = i;
			}

		}
		if (min != j)
			swap(wektor.at(j), wektor.at(min));
	}
}


void SortowaniePrzezZlicznie(vector<int> &wektor, int sz) {  //nie bede sie rozwodzil nad dzialaniem algorytmow sortujacych bo to by zajelo 30 minut a to wiedza dostepna w sekunde w google
	int i, j, k;
	int idx = 0;
	int min, max;

	min = max = wektor.at(0);
	for (i = 1; i < sz; i++) {
		min = (wektor.at(i) < min) ? wektor.at(i) : min;  //skrocona forma if else..
		max = (wektor.at(i) > max) ? wektor.at(i) : max;
	}

	k = max - min + 1;

	int *B = new int[k];
	for (i = 0; i < k; i++) B[i] = 0;

	for (i = 0; i < sz; i++) {
		B[wektor.at(i) - min]++;
	}

	for (i = min; i <= max; i++) {
		for (j = 0; j < B[i - min]; j++) wektor.at(idx++) = i;
	}

	delete[] B;
}

int max_liczba(vector<int> wejscie, int rozmiar) // zwrocenie max liczby z vectora
{
	int max = wejscie.at(0);
	for (int i = 1; i < rozmiar; i++) //szukanie maxa
	{
		if (max < wejscie.at(i))
			max = wejscie.at(i);
	}
	return max;
}




int qsort_rozdzielanie(std::vector<int> &arr, const int left, const int right) //podzial vectora quicksorta
{
	const int mid = left + (right - left) / 2;
	const int pivot = arr[mid];

	std::swap(arr[mid], arr[left]);
	int i = left + 1;
	int j = right;
	while (i <= j)
	{
		while (i <= j && arr[i] <= pivot)
			i++;

		while (i <= j && arr[j] > pivot)
			j--;

		if (i < j)
			std::swap(arr[i], arr[j]);
	}
	std::swap(arr[i - 1], arr[left]);
	return i - 1;
}

void qsort(std::vector<int> &arr, const int left, const int right) //nie bede sie rozwodzil nad dzialaniem algorytmow sortujacych bo to by zajelo 30 minut a to wiedza dostepna w sekunde w google
{
	if (left >= right) return;
	int podzial = qsort_rozdzielanie(arr, left, right);
	qsort(arr, left, podzial - 1);
	qsort(arr, podzial + 1, right);
}

void my_qsort(std::vector<int> &arr)
{
	qsort(arr, 0, arr.size() - 1);
}

void WybierzZbiorA(vector<int> &ZbiorA) {  //wypelnia vektor ze zbioru podanego w wymaganiach projektu
	ZbiorA.erase(ZbiorA.begin(), ZbiorA.end());  ZbiorA.clear();
	for (int i = 0; i <= 100000; i++) {
		ZbiorA.push_back(rand() % 100000);
	}

}

void WybierzZbiorA10000(vector<int> &ZbiorA) {  //wypelnia vektor ze zbioru podanego w wymaganiach projektu
	ZbiorA.erase(ZbiorA.begin(), ZbiorA.end());  ZbiorA.clear();
	for (int i = 0; i <= 10000; i++) {
		ZbiorA.push_back(rand() % 10000);
	}

}

void WybierzZbiorB(vector<int> &ZbiorB) {  //wypelnia vektor ze zbioru podanego w wymaganiach projektu
	ZbiorB.erase(ZbiorB.begin(), ZbiorB.end());  ZbiorB.clear();
	ZbiorB.push_back(100000);
	for (int i = 1; i <= 99999; i++) {
		ZbiorB.push_back(i);
	}
	ZbiorB.push_back(0);
}

void WybierzZbiorB10000(vector<int> &ZbiorB) {  //wypelnia vektor ze zbioru podanego w wymaganiach projektu
	ZbiorB.erase(ZbiorB.begin(), ZbiorB.end());  ZbiorB.clear();
	ZbiorB.push_back(10000);
	for (int i = 1; i <= 9999; i++) {
		ZbiorB.push_back(i);
	}
	ZbiorB.push_back(0);
}

void WybierzZbiorC(vector<int> &ZbiorA) {  //wypelnia vektor ze zbioru podanego w wymaganiach projektu
	ZbiorA.erase(ZbiorA.begin(), ZbiorA.end());  ZbiorA.clear();
	for (int i = 100000; i >= 0; i--) {
		ZbiorA.push_back(i);
	}

}


void WybierzZbiorC10000(vector<int> &ZbiorA) { //wypelnia vektor ze zbioru podanego w wymaganiach projektu
	ZbiorA.erase(ZbiorA.begin(), ZbiorA.end());  ZbiorA.clear();
	for (int i = 10000; i >= 0; i--) {
		ZbiorA.push_back(i);
	}

}

void CombineAll() {
	fstream file; //tworzy uchwyt do pliku
	file.open("wynik.txt", std::ios::app); //otwieranie pliku w trybie append czyli dopisywania tekstu

	vector<int> dane; //vector w ktorym beda przechowywane randomowe liczby
	WybierzZbiorA(dane);  //wypelnienie vectora danym zbiorem
	std::cout << "Zbior a:\n";
	file << "Zbior a:\n";  //zapis do pliku tekstu
	std::cout << "\n\tRozpoczecie QuickSort\n";
	std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now(); //start licznika do mierzenia czasu algorytmu
	my_qsort(dane); //wykonanie funkcji sortujacej
	std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now(); //stop stopera
	std::cout << "\t  Czas = " << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() <<"ms"<< std::endl; //obliczanie i wypisanie czasu wykonania
	file << "\tCzas quicksort : ";
	file << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count();  //zapis do pliku....
	file << "ms\n";
	std::cout << "\tZakonczenie QuickSort";
	  //TO SAMO CO WYŻEJ TYLKO DLA INNYCH ALGORYTMOW
	std::cout << "\n\tRozpoczecie sortowania przez zliczanie\n";
	begin = std::chrono::steady_clock::now();
	WybierzZbiorA(dane);
	SortowaniePrzezZlicznie(dane, dane.size());
	end = std::chrono::steady_clock::now();
	std::cout << "\t  Czas = " << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() << "ms" << std::endl;
	file << "\tCzas sortowania przez zliczanie : ";
	file << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count();
	file << "ms\n";
	std::cout << "\tZakonczenie sortowania przez zliczanie\n";

	std::cout << "\n\tRozpoczecie sortowania przez wybor (10 000 elementow poniewaz 100 000 trwa zbyt dlugo)\n";
	begin = std::chrono::steady_clock::now();
	WybierzZbiorA10000(dane);
	selectionSort(dane, dane.size());
	end = std::chrono::steady_clock::now();
	std::cout << "\t  Czas = " << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() << "ms" << std::endl;
	file << "\tCzas sortowania przez wybor (10 000 elementow) : ";
	file << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count();
	file << "ms\n";
	std::cout << "\tZakonczenie sortowania przez wybor\n";

	std::cout << "\n\tRozpoczecie sortowania domyslnego\n";
	begin = std::chrono::steady_clock::now();
	WybierzZbiorA(dane);
	std::sort(dane.begin(), dane.end());
	end = std::chrono::steady_clock::now();
	std::cout << "\t  Czas = " << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() << "ms" << std::endl;
	file << "\tCzas sortowania domyslnego : ";
	file << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count();
	file << "ms\n";
	std::cout << "\tZakonczenie sortowania domyslnego\n\n";

	std::cout << "\nZbior b:\n";
	file << "\nZbior b:\n";
	WybierzZbiorB(dane);
	std::cout << "\n\tRozpoczecie QuickSort\n";
	begin = std::chrono::steady_clock::now();
	my_qsort(dane);
	end = std::chrono::steady_clock::now();
	std::cout << "\t  Czas = " << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() <<"ms"<< std::endl;
	file << "\tCzas quicksort : ";
	file << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count();
	file << "ms\n";
	std::cout << "\tZakonczenie QuickSort\n";

	std::cout << "\n\tRozpoczecie sortowania przez zliczanie\n";
	begin = std::chrono::steady_clock::now();
	WybierzZbiorB(dane);
	SortowaniePrzezZlicznie(dane, dane.size());
	end = std::chrono::steady_clock::now();
	std::cout << "\t  Czas = " << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() <<"ms"<< std::endl;
	file << "\tCzas sortowania przez zliczanie : ";
	file << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count();
	file << "ms\n";
	std::cout << "\tZakonczenie sortowania przez zliczanie\n";

	std::cout << "\n\tRozpoczecie sortowania przez wybor (10 000 elementow bo 100 000 za dlugo trwa)\n";
	begin = std::chrono::steady_clock::now();
	WybierzZbiorB10000(dane);
	selectionSort(dane, dane.size());
	end = std::chrono::steady_clock::now();
	std::cout << "\t  Czas = " << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() <<"ms"<< std::endl;
	file << "\tCzas sortowania przez wybor (10 000 elementow) : ";
	file << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count();
	file << "ms\n";
	std::cout << "\tZakonczenie sortowania przez wybor\n";

	std::cout << "\n\tRozpoczecie sortowania domyslnego\n";
	begin = std::chrono::steady_clock::now();
	WybierzZbiorB(dane);
	std::sort(dane.begin(), dane.end());
	end = std::chrono::steady_clock::now();
	std::cout << "\t  Czas = " << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() <<"ms"<< std::endl;
	file << "\tCzas sortowania domyslnego: ";
	file << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count();
	file << "ms\n";
	std::cout << "\tZakonczenie sortowania domyslnego\n\n";


	std::cout << "Zbior C:\n";
	file << "\nZbior c:\n";
	std::cout << "\n\tRozpoczecie QuickSort\n";
	WybierzZbiorC(dane);
	begin = std::chrono::steady_clock::now();
	my_qsort(dane);
	end = std::chrono::steady_clock::now();
	std::cout << "\t  Czas = " << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() <<"ms"<< std::endl;
	file << "\tCzas quicksort: ";
	file << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count();
	file << "ms\n";
	std::cout << "\tZakonczenie QuickSort\n";

	std::cout << "\n\tRozpoczecie sortowania przez zliczanie\n";
	begin = std::chrono::steady_clock::now();
	WybierzZbiorC(dane);
	SortowaniePrzezZlicznie(dane, dane.size());
	end = std::chrono::steady_clock::now();
	std::cout << "\t  Czas = " << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() <<"ms"<< std::endl;
	file << "\tCzas sortowania przez zliczanie: ";
	file << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count();
	file << "ms\n";
	std::cout << "\tZakonczenie sortowania przez zliczanie\n";

	std::cout << "\n\tRozpoczecie sortowania przez wybor (10 000 bo 100 000 za dlugo trwa)\n";
	begin = std::chrono::steady_clock::now();
	WybierzZbiorC10000(dane);
	selectionSort(dane, dane.size());
	end = std::chrono::steady_clock::now();
	std::cout << "\t  Czas = " << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() <<"ms"<< std::endl;
	file << "\tCzas sortowania przez wybor (10 000 elementow): ";
	file << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count();
	file << "ms\n";
	std::cout << "\tZakonczenie sortowania przez wybor\n";

	std::cout << "\n\tRozpoczecie sortowania domyslnego\n";
	begin = std::chrono::steady_clock::now();
	WybierzZbiorC(dane);
	std::sort(dane.begin(), dane.end());
	end = std::chrono::steady_clock::now();
	file << "\tCzas sortowania domyslnego: ";
	file << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count();
	file << "ms\n";
	std::cout << "\t  Czas = " << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() <<"ms"<< std::endl;
	std::cout << "\tZakonczenie sortowania domyslnego";

	file.close();

}

int main()
{
	srand(time(NULL));
	vector<int> Zbior;

	int choose;
	cout << "Wybierz sortowanie: \n\n\t0.Wszystkie kombinacje + podsumowanie czasu w pliku txt\n\n\tZbior A: \n\t\t1.Quick sort\n\t\t2.Counting sort\n\t\t3.Sortowanie przez wybor\n\t\t4.Sortowanie domyslne";
	cout << "\n\tZbior B : \n\t\t5.Quick sort\n\t\t6.Counting sort\n\t\t7.Sortowanie przez wybor\n\t\t8.Sortowanie domyslne";
	cout << "\n\tZbior C : \n\t\t9.Quick sort\n\t\t10.Counting sort\n\t\t11.Sortowanie przez wybor\n\t\t12.Sortowanie domyslne\n\t-->";


	cin >> choose; //proste menu
	switch (choose) {
	case 0:
		CombineAll();
		break;
	case 1:
		WybierzZbiorA(Zbior);
		my_qsort(Zbior);
		break;
	case 2:
		WybierzZbiorA(Zbior);
		SortowaniePrzezZlicznie(Zbior, Zbior.size());
		break;
	case 3:
		WybierzZbiorA(Zbior);
		selectionSort(Zbior, Zbior.size());
		break;
	case 4:
		WybierzZbiorA(Zbior);
		std::sort(Zbior.begin(), Zbior.end());
		break;
	case 5:
		WybierzZbiorB(Zbior);
		my_qsort(Zbior);
		break;
	case 6:
		WybierzZbiorB(Zbior);
		SortowaniePrzezZlicznie(Zbior, Zbior.size());
		break;
	case 7:
		WybierzZbiorB(Zbior);
		selectionSort(Zbior, Zbior.size());
		break;
	case 8:
		WybierzZbiorB(Zbior);
		std::sort(Zbior.begin(), Zbior.end());
		break;
	case 9:
		WybierzZbiorC(Zbior);
		my_qsort(Zbior); //quicksort
		break;
	case 10:
		WybierzZbiorC(Zbior);
		SortowaniePrzezZlicznie(Zbior, Zbior.size()); //...
		break;
	case 11:
		WybierzZbiorC(Zbior);
		selectionSort(Zbior, Zbior.size()); //sortowanie przez wybor
		break;
	case 12:
		WybierzZbiorC(Zbior);
		std::sort(Zbior.begin(), Zbior.end()); //defaultowa funkcja sortujaca
		break;
	}



	//for (int i = 0; i < Zbior.size(); i++)
		//std::cout << Zbior.at(i) << " ,";

	system("pause");
	return 0;
}