#include "stdafx.h"
#include <stdio.h>
#include <time.h>
#include <iostream>
#include <iomanip>
#include <ctime>
#include <conio.h>
#include <stdlib.h>
#include <cstdlib> 

using namespace std;

int pos[100];
int pos_ind[100];
int neg[100];

int comp_bubble = 0, change_bubble = 0;
int comp_select = 0, change_select = 0;
int comp_insert = 0, change_insert = 0;
int comp_shell = 0, change_shell = 0;

void copy(int from[][100], int to[][100], int height, int width)
{
	int i, j;
	for (i = 0; i<height; i++)
	{
		for (j = 0; j<width; j++)
		{
			to[i][j] = from[i][j];
		}
	}
}

void print_matrix(int m[][100], int height, int width)
{

	int i, j;
	for (i = 0; i<height; i++)
	{
		for (j = 0; j<width; j++)
		{
			printf("%4d", m[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

int del_pos(int a[], int width) //удаление неотрицательных значений и возврат их номера
{
	int j, n = 0;

	for (j = 0; j<width; j++)
	{
		if (a[j] >= 0)
		{
			pos_ind[n] = j;
			pos[n] = a[j];
			n++;
		}
		else
		{
			a[j - n] = a[j];
		}
	}
	return n;
}

void restore(int a[], int width, int num_positives) // восстановление после выполнения предыдущего блока
{
	int last_pos_ind = 0, next_pos_ind;
	int i, j = 0;
	for (i = 0; i<width; i++) neg[i] = a[i];
	for (i = 0; i<num_positives; i++) // i - индекс положительных значений 
	{
		for (j = width - 1; j >= pos_ind[i]; j--)
		{
			a[j + 1] = a[j];
		}
		a[pos_ind[i]] = pos[i];
	}
}

void bubble_sorting(int a[100], int width)
{
	int j, h = width - 1;
	int sorting_finished = 1;
	int temp;

	if (width <= 1) return;

	do
	{
		sorting_finished = 1;
		for (j = 0; j<h; j++)
		{
			comp_bubble++;
			if (a[j] > a[j + 1])
			{
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
				sorting_finished = 0;
				change_bubble++;
			}
		}
		h--;
	} while (sorting_finished == 0);
}

void select_sorting(int a[100], int width)
{
	int temp, smallest_ind, j, k;

	if (width <= 1) return;

	for (j = 0; j<width - 1; j++)
	{
		smallest_ind = j;
		for (k = j + 1; k<width; k++)
		{
			if (a[k]<a[smallest_ind]) smallest_ind = k;
			comp_select++;
		}
		if (smallest_ind != j)
		{
			temp = a[j];
			a[j] = a[smallest_ind];
			a[smallest_ind] = temp;
			change_select++;
		}
	}
}

void insert_sorting(int a[100], int width)
{
	int j, k;
	int temp;

	if (width <= 1) return;

	for (j = 1; j < width; j++)
	{
		temp = a[j];
		for (k = j - 1; k >= 0; k--)
		{
			comp_insert++;
			if (temp >= a[k]) break;
			a[k + 1] = a[k];
			a[k] = temp;
			change_insert++;
		}
	}

}

void shell_sorting(int a[100], int width)
{
	int j, distance = width / 2, temp, sorting_finished = 0;

	if (width <= 1) return;

	do
	{
		if (distance == 1) sorting_finished = 1;
		for (j = 0; j<width - distance; j++)
		{
			if (a[j] > a[j + distance])
			{
				temp = a[j];
				a[j] = a[j + distance];
				a[j + distance] = temp;
				sorting_finished = 0;
				change_shell++;
			}
			comp_shell++;
		}
		if (distance>1) distance--;
	} while (sorting_finished == 0);
}




int main(int argc, char **argv)
{
	setlocale(LC_ALL, "Russian");
	srand(time(NULL));

	int matrix[100][100];
	int for_sorting[100][100];
	double height_d, width_d;
	int height, width;
	int i, j;
	int n;
	cout << "Введите число строк\n";
	cin >> height_d;
	cout << "Введите число столбцов\n";
	cin >> width_d;

	if (height_d != (int)height_d || width_d != (int)width_d || height_d <= 0 || width_d <= 0)
	{
		cout << "Ошибка ввода\n";
		return 0;
	}
	height = (int)height_d;
	width = (int)width_d;

	for (i = 0; i<height; i++)
	{
		for (j = 0; j<width; j++) matrix[i][j] = -99 + rand() % 120;
	}

	cout << "Неотсортированная матрица:\n";
	print_matrix(matrix, height, width);


	copy(matrix, for_sorting, height, width);

	for (i = 0; i<height; i++)
	{
		n = del_pos(for_sorting[i], width);
		bubble_sorting(for_sorting[i], width - n);
		restore(for_sorting[i], width, n);
	}

	cout << "Сортировка пузырьковым методом:\n";
	print_matrix(for_sorting, height, width);



	copy(matrix, for_sorting, height, width);

	for (i = 0; i<height; i++)
	{
		n = del_pos(for_sorting[i], width);
		select_sorting(for_sorting[i], width - n);
		restore(for_sorting[i], width, n);
	}

	cout << "Сортировка методом отбора:\n";
	print_matrix(for_sorting, height, width);


	copy(matrix, for_sorting, height, width);

	for (i = 0; i<height; i++)
	{
		n = del_pos(for_sorting[i], width);
		insert_sorting(for_sorting[i], width - n);
		restore(for_sorting[i], width, n);
	}

	cout << "Сортировка методом вставки:\n";
	print_matrix(for_sorting, height, width);


	copy(matrix, for_sorting, height, width);

	for (i = 0; i<height; i++)
	{
		n = del_pos(for_sorting[i], width);
		shell_sorting(for_sorting[i], width - n);
		restore(for_sorting[i], width, n);
	}

	cout << "Сортировка методом Шелла:\n";
	print_matrix(for_sorting, height, width);


	printf("--------------------------------------------------\n");
	printf("|      Метод       |  Сравнения  |   Изменения   |\n");
	printf("--------------------------------------------------\n");
	printf("|      Пузырьковый |    %5d    |     %5d     |\n", comp_bubble, change_bubble);
	printf("|      Отбор       |    %5d    |     %5d     |\n", comp_select, change_select);
	printf("|      Вставка     |    %5d    |     %5d     |\n", comp_insert, change_insert);
	printf("|      Шелла       |    %5d    |     %5d     |\n", comp_shell, change_shell);
	printf("--------------------------------------------------\n");

	system("pause");
	return 0;
}