#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <iomanip>
#include <ctime>
#include <algorithm>
#include <windows.h>
#include <malloc.h>

enum SortsType
{
	BUBBLE,
	SELECTION,
	INSERTS,
	SHELL,
	QUICK
};

#undef max

int **INITIAL;
int **WORK;

int n, m;

unsigned permutations[5];
unsigned comparisions[5];

unsigned SumOfNumbers(int elem);

void BubbleSort();
void SelectionSort();
void InsertsSort();
void ShellSort();
void QuickSort(int** arr, unsigned column, int left, int right);

void ShowRetry();

void main()
{
begin:	for (;;)
	{
		std::cout << "Enter \"n\" and \"m\" between 1 and 15" << std::endl;
		std::cout << "n =  ";
		if (!(std::cin >> n) || n < 1 || n > 15)
		{
			std::cin.clear();
			std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
			std::cout << "Error! Incorrect number" << std::endl;
			continue;
		}
		std::cout << "m = ";
		if (!(std::cin >> m) || m < 1 || m > 15)
		{
			std::cin.clear();
			std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
			std::cout << "Error! Incorrect number" << std::endl;
			continue;
		}
		break;
	}
	srand(time(0));
	INITIAL = new int*[n];
	WORK = new int*[n];
	for (int i = 0; i < n; i++)
	{
		INITIAL[i] = new int[m];
		WORK[i] = new int[m];
		for (int j = 0; j < m; j++)
		{
			INITIAL[i][j] = rand() % 201 - 100;
			WORK[i][j] = INITIAL[i][j];
		}
	}
	std::cout << "\nInitial array:\n" << std::endl;
	ShowRetry();
	BubbleSort();
	std::cout << "\nBubble:\n" << std::endl;
	ShowRetry();
	SelectionSort();
	std::cout << "\nSelection:\n" << std::endl;
	ShowRetry();
	InsertsSort();
	std::cout << "\nInserts:\n" << std::endl;
	ShowRetry();
	ShellSort();
	std::cout << "\nShell:\n" << std::endl;
	ShowRetry();
	for (int j = 0; j < m; j++)
		QuickSort(WORK, j, 0, n - 1);
	std::cout << "\nQuick:\n" << std::endl;
	ShowRetry();
	printf("\n--------------------------------------------\n");
	printf("|%10s|%15s|%15s|\n", "Method", "Permutations", "Comparisons");
	printf("--------------------------------------------\n");
	printf("|%10s|%15d|%15d|\n", "Bubble", permutations[BUBBLE], comparisions[BUBBLE]);
	printf("|%10s|%15d|%15d|\n", "Selection", permutations[SELECTION], comparisions[SELECTION]);
	printf("|%10s|%15d|%15d|\n", "Inserts", permutations[INSERTS], comparisions[INSERTS]);
	printf("|%10s|%15d|%15d|\n", "Shell", permutations[SHELL], comparisions[SHELL]);
	printf("|%10s|%15d|%15d|\n", "Quick", permutations[QUICK], comparisions[QUICK]);
	printf("--------------------------------------------\n");
rep:	std::cout << "\nRepeat? 0 - no, 1 - yes" << std::endl;
	short repeat = -1;
	std::cin >> repeat;
	if ((repeat == 1) || (repeat == 0))
	{
		if (repeat == 1)
		{
			memset(permutations, 0, sizeof(unsigned) * 5);
			memset(comparisions, 0, sizeof(unsigned) * 5);
			goto begin;
		}
	}
	else
	{
		std::cin.clear();
		std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
		std::cout << "\nError! Incorrect number\n" << std::endl;
		goto rep;
	}
}

unsigned SumOfNumbers(int elem)
{
	elem = abs(elem);
	if (elem == 0)
		return 0;
	return SumOfNumbers(elem / 10) + (elem % 10);
}

void BubbleSort()
{
	bool flag;
	for (int j = 0; j < m; j++)
	{
		for (int k = 0; k < n - 1; ++k)
		{
			flag = false;
			for (int i = 0; i < n - k - 1; i++)
			{
				if (SumOfNumbers(WORK[i][j]) > SumOfNumbers(WORK[i + 1][j]))
				{
					std::swap(WORK[i][j], WORK[i + 1][j]);
					++permutations[BUBBLE];
					flag = true;
				}
				++comparisions[BUBBLE];
			}
			if (!flag) break;
		}
	}
}
void SelectionSort()
{
	int minimum, index;
	for (int j = 0; j < m; j++)
		for (int i = 0; i < n - 1; i++)
		{
			minimum = WORK[i][j];
			index = i;
			for (int k = i + 1; k < n; ++k)
			{
				++comparisions[SELECTION];
				if (SumOfNumbers(minimum) > SumOfNumbers(WORK[k][j]))
				{
					minimum = WORK[k][j];
					index = k;
				}
			}
			if (i != index)
			{
				std::swap(WORK[i][j], WORK[index][j]);
				++permutations[SELECTION];
			}
		}
}
void InsertsSort()
{
	int k, tmp;
	for (int j = 0; j < m; j++)
		for (int i = 1; i < n; i++)
		{
			tmp = WORK[i][j];
			for (k = i - 1; k >= 0; k--)
			{
				++comparisions[INSERTS];
				if (SumOfNumbers(tmp) >= SumOfNumbers(WORK[k][j]))
					break;
				WORK[k + 1][j] = WORK[k][j];
			}
			if (i != k + 1)
			{
				WORK[k + 1][j] = tmp;
				++permutations[INSERTS];
			}
		}
}
void ShellSort()
{
	int tmp, step;
	for (int j = 0; j < m; j++)
		for (step = (n / 2) + (n % 2); step > 0; --step)
			for (int k = 0; k < n - step; ++k)
			{
				if (SumOfNumbers(WORK[k][j]) > SumOfNumbers(WORK[k + step][j]))
				{
					std::swap(WORK[k][j], WORK[k + step][j]);
					++permutations[SHELL];
				}
				++comparisions[SHELL];
			}
}

void QuickSort(int** arr, unsigned column, int left, int right)
{
	int i = left, j = right;
	const unsigned idx = (left + right) / 2;
	int avg = arr[idx][column];
	while (i <= j)
	{
		while (SumOfNumbers(arr[i][column]) < SumOfNumbers(avg))
		{
			if (idx != i)
				++comparisions[QUICK];
			++i;
		}
		if (idx != i)
			++comparisions[QUICK];
		while (SumOfNumbers(arr[j][column]) > SumOfNumbers(avg))
		{
			if (idx != j)
				++comparisions[QUICK];
			--j;
		}
		if (idx != j)
			++comparisions[QUICK];
		if (i <= j)
		{
			if (i != j)
				++permutations[QUICK];
			std::swap(arr[i][column], arr[j][column]);
			++i;
			--j;
		}
	};
	if (left < j)
		QuickSort(arr, column, left, j);
	if (i < right)
		QuickSort(arr, column, i, right);
}

void ShowRetry()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			printf("%4d ", WORK[i][j]);
			WORK[i][j] = INITIAL[i][j];
		}
		std::cout << std::endl;
	}
}