#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <time.h>
#include <math.h>

using namespace std;

int *sortedNumbers(int n)
{
	int *table = new int[n];
	for (int i = 0; i < n; ++i)
		table[i] = i;
	return table;
}

int *randomNumbers(int n)
{
	int *table = new int[n];
	for (int i = 0; i < n; ++i)
		table[i] = rand();
	return table;
}

void swap(int &a, int &b)
{
	int tmp = a;
	a = b;
	b = tmp;
}

int *partlyRandomNumbers(int n, int m)
{
	int *table = sortedNumbers(n);
	for (int i = 0; i < m; ++i)
	{
		int ii = rand() % n;
		int jj = rand() % n;
		while (ii != jj)
			jj = rand() % n;
		swap(table[ii], table[jj]);
	}
	return table;
}

typedef void(*Sortowanie)(int *tab, int ilosc, int &licznik1, int &licznik2);

void sortowanie1(int *tab, int ilosc, int &porownania, int &zamiany)
{
	//Sortowanie babelkowe
	porownania = 0;
	zamiany = 0;

	for (int j = 0; j<ilosc - 1; j++)
	{
		for (int i = 0; i<ilosc - 1; i++)
		{
			if (tab[i]>tab[i + 1])
			{
				swap(tab[i], tab[i + 1]);
				zamiany++;
			}
			porownania++;

		}
	}
}

void sortowanie2(int *tab, int ilosc, int &porownania, int &zamiany)
{
	//Sortowanie przez kopcowanie
	porownania = 0;
	zamiany = 0;
	int i, j, k, m, x;

	for (i = 2; i <= ilosc; i++)
	{
		j = i; k = j / 2;
		x = tab[i];
		while ((k > 0) && (tab[k] < x))
		{
			tab[j] = tab[k];
			j = k; k = j / 2;
			porownania++;
		}
		tab[j] = x;
	}

	for (i = ilosc; i>1; i--)
	{
		swap(tab[1], tab[i]);
		zamiany++;
		j = 1; k = 2;

		while (k < i)
		{
			porownania++;
			if ((k + 1 < i) && (tab[k + 1] > tab[k]))
			{
				m = k + 1;
			}
			else
				m = k;

			porownania++;
			if (tab[m] <= tab[j])
			{
				break;
			}
			swap(tab[j], tab[m]);
			zamiany++;
			j = m;
			k = j + j;
			porownania++;
		}
	}
}

void sortowanie3(int *tab, int ilosc, int &porownania, int &zamiany)
{
	//Sortowanie przez scalanie
	porownania = 0;
	zamiany = 0;


}

void sortowanie4(int *tab, int ilosc, int &porownania, int &zamiany)
{
	//Sortowanie quicksort
	porownania = 0;
	zamiany = 0;


}

void sortowanie5(int *tab, int ilosc, int &porownania, int &zamiany)
{
	//Sortowanie przez wybór
	porownania = 0;
	zamiany = 0;
	int j, pmin;

	for (j = 0; j < ilosc - 1; j++)
	{
		pmin = j;
		for (int i = j + 1; i < ilosc; i++)
		{
			porownania++;
			if (tab[i] < tab[pmin])
			{
				pmin = i;
			}
			swap(tab[pmin], tab[j]);
			zamiany++;
		}
	}
}

void sortowanie6(int *tab, int ilosc, int &porownania, int &zamiany)
{
	//Sortowanie przez wstawianie
	porownania = 0;
	zamiany = 0;
	int i, j, x;
	for (j = ilosc - 2; j >= 0; j--)
	{
		x = tab[j];
		i = j + 1;
		while ((i < ilosc) && (x > tab[i]))
		{
			tab[i - 1] = tab[i];
			i++;
		}
		porownania++;
		tab[i - 1] = x;
	}
}

int main()
{
	int *table1 = sortedNumbers(50);
	int *table2 = sortedNumbers(500);
	int *table3 = sortedNumbers(2000);

	int *table4 = randomNumbers(50);
	int *table5 = randomNumbers(500);
	int *table6 = randomNumbers(2000);

	int *table7 = partlyRandomNumbers(50, 10);
	int *table8 = partlyRandomNumbers(500, 50);
	int *table9 = partlyRandomNumbers(2000, 200);

	int* tables[9] = {
		table1, table2, table3,
		table4, table5, table6,
		table7, table8, table9
	};

	int ilosci[9] = {
		50, 500, 2000,
		50, 500, 2000,
		50, 500, 2000
	};

	Sortowanie funkcje[6] = {
		sortowanie1,
		sortowanie2,
		sortowanie3,
		sortowanie4,
		sortowanie5,
		sortowanie6
	};

	for (int j = 0; j < 6; ++j)
	{
		cout << endl << "Sortowanie " << (j + 1) << ":" << endl;
		cout << "\tPorownania:\tZamiany:\tCzas dzialania:" << endl;

		for (int i = 0; i < 9; ++i)
		{
			int porownania = 0;
			int zamiany = 0;

			Sortowanie sortowanie = funkcje[j];

			clock_t t1 = clock();
			sortowanie(tables[i], ilosci[i], porownania, zamiany);
			clock_t t2 = clock();

			double czas = ((double)(t2 - t1)) / CLOCKS_PER_SEC;

			cout << i+1 << ".\t" << porownania << "\t\t" << zamiany << "\t\t" << czas << endl;
		}
	}

	/*for (int i = 0; i < 50; i++)
		{
			cout << table1[i] << " ";
		}*/

	system("pause");
	return 0;
}