#include "stdafx.h"
#include "math.h"
#include <iostream>
#include <time.h>
#include <windows.h>
#include <stdio.h>
#include <conio.h>
long sravnii[5];
long perestanovok[5];
using namespace std;

HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void bubble_sort(int N,int M, int **arr) //Функция пузырьковой сортировки
{
	HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
	SetConsoleTextAttribute(hStdout, 10);
	printf("\nPuzirek sort\n");
	SetConsoleTextAttribute(hStdout, 15);
	int sravnenii = 0, obmenov = 0;
	int mas[100];
	int count = 0;
	for (int i=0; i<M; i++)
	{
		count=0;
		for (int j=0;j<N;j++)
		{
			if (arr[j][i]%2==0) //Проверка элемента массива на четность
			{
				mas[count]=arr[j][i];//Создание нового массива из четных элементов
				count++;
			}
		}

		for (int j=0; j<count; j++)//Пузырьковая сортировка нового массива
			for (int k=1; k<count; k++)
			{
				if (mas[k-1] < mas[k])
				{
				swap (mas[k-1], mas[k]);
				++obmenov;
				}
				++sravnenii;
			}

		count=0;

		for (int j=0;j<N;j++)
		{
			if (arr[j][i]%2==0)
			{
			arr[j][i]=mas[count];
			count++;
			}
		}
	}

	for (int i=0; i<N; ++i)
	{
		for (int j=0; j<M; ++j)
			printf (" %4.1d ", arr[i][j]);

		printf ("\n");
	}

	SetConsoleTextAttribute(hStdout, 23);
	printf ("sravneniy: %d, obmenov: %d.\n", sravnenii, obmenov);
	sravnii[0]=sravnenii;
	perestanovok[0]=obmenov;
}
/////////////////////////////////////////////////Сортировка пузырем////////////////////////////////////////////////////////////////
void select(int N,int M, int **arr) //Функция сортировки отбора
{
	HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
	SetConsoleTextAttribute(hStdout, 10);
	printf("\nSort otbor\n");
	SetConsoleTextAttribute(hStdout, 15);
	int sravnenii = 0,  obmenov = 0;
	int mas[100];
	int count = 0;
	for (int i=0; i<M; ++i)
	{
		count=0;
		for (int j=0;j<N;j++)
		{
			if (arr[j][i]%2==0)
			{
				mas[count]=arr[j][i];
				count++;
			}
		}

		for (int j=0; j<count; j++)
		{
			int sel = j;
			for (int k=j; k<count; k++)
			{
				if (mas[k] > mas[sel])
				sel = k;
				++sravnenii;
			}
			swap (mas[sel], mas[j]);
			++obmenov;
		}

		count=0;
    	for (int j=0;j<N;j++)
		{
			if (arr[j][i]%2==0)
			{
				arr[j][i]=mas[count];
				count++;
			}
		}
	}
	for (int i=0; i<N; ++i)
	{
		for (int j=0; j<M; ++j)
			printf (" %4.1d ", arr[i][j]);
		printf ("\n");
	}
	SetConsoleTextAttribute(hStdout, 23);
	printf ("sravneniy: %d,  obmenov: %d.\n",sravnenii, obmenov);
	sravnii[1]=sravnenii;
	perestanovok[1]=obmenov;}
/////////////////////////////////////////////////Сортировкa вставка////////////////////////////////////////////////////////////////
void insert(int N,int M, int **arr)
{
	HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
	SetConsoleTextAttribute(hStdout, 10);
	printf("\nSort vstavka.\n");
	SetConsoleTextAttribute(hStdout, 15);
	int sravnenii = 0,  obmenov = 0;
	int mas[100];
	int count = 0;
	for (int i=0; i<M; ++i)
	{
		count=0;
		for (int j=0;j<N;j++)
		{
			if (arr[j][i]%2==0)
			{
				mas[count]=arr[j][i];
				count++;
			}
		}

		for (int j=0; j<count; j++)
		{	int x = mas[j];
			int k;
			for (k=j; k>0 && mas[k-1]<x; k--)
			{	mas[k] = mas[k-1];
				++sravnenii,  ++obmenov;
			}
			mas[k] = x;
			++obmenov;
		}
		count=0;
    	for (int j=0;j<N;j++)
		{
			if (arr[j][i]%2==0)
			{
				arr[j][i]=mas[count];
				count++;
			}
		}
	}
	for (int i=0; i<N; ++i)
	{
		for (int j=0; j<M; ++j)
			printf (" %4.1d ", arr[i][j]);
		printf ("\n");
	}
	SetConsoleTextAttribute(hStdout, 23);
	printf ("sravneniy: %d,  obmenov: %d.\n",sravnenii, obmenov);
	sravnii[2]=sravnenii;
	perestanovok[2]=obmenov;}
/////////////////////////////////////////////////Сортировкa Шелла//////////////////////////////////////////////////////////////////
void shell (int N,int M, int **arr)
{
	HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
	SetConsoleTextAttribute(hStdout, 10);
	printf("\nSort Shell.\n");
	SetConsoleTextAttribute(hStdout, 15);
	int sravnenii = 0,  obmenov = 0;
	int mas[100];
	int count = 0;
	for (int i=0; i<M; ++i)
	{
		count=0;
		for (int j=0;j<N;j++)
		{
			if (arr[j][i]%2==0)
			{
				mas[count]=arr[j][i];
				count++;
			}
		}
		for (int j=0; j+1<count; j++)
		{
			++sravnenii;
			if (mas[j+1] < mas[j])
			{
				swap (mas[j+1], mas[j]);
				++obmenov;
			}
		}
		for (int j=0; j+1<count; j++)
		{
			++sravnenii;
			if (mas[j] < mas[j+1])
			{
				swap (mas[j], mas[j+1]);
				++obmenov;
			}
		}
		for (;;)
		{
			bool any = false;
			for (int j=0; j<count; j++)
			for (int k=1; k<count; k++)
			{
				if (mas[k-1] < mas[k])
				{
					swap (mas[k-1], mas[k]);
					++obmenov;
				}
				++sravnenii;
			}
			if (!any)  break;
		}

		count=0;
    	for (int j=0;j<N;j++)
		{
			if (arr[j][i]%2==0)
			{
				arr[j][i]=mas[count];
				count++;
			}
		}
	}

	for (int i=0; i<N; ++i)
	{
		for (int j=0; j<M; ++j)
			printf (" %4.1d ", arr[i][j]);
		printf ("\n");
	}
	SetConsoleTextAttribute(hStdout, 23);
	printf ("sravneniy: %d,  obmenov: %d.\n",sravnenii, obmenov);
	sravnii[3]=sravnenii;
	perestanovok[3]=obmenov;}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void quick_sort (int a[50], int l, int r, int & sravnenii, int & obmenov)
{
int i = l, j = r;
int x = a[(l+r)/2];
++obmenov;
do
{
	++sravnenii;
while (a[i] > x)
{
i++;
++sravnenii;
}
++sravnenii;
while (x > a[j])
{
j--;
++sravnenii;
}
if (i <= j)
{
	swap ( a[i++],a[j--]);
++obmenov;
}
}while (i <= j);
if (i < r)
quick_sort (a, i, r,sravnenii, obmenov);
if (l < j)
quick_sort (a, l, j, sravnenii, obmenov);}
/////////////////////////////////////////////////Быстрая сортировка////////////////////////////////////////////////////////////////
void qs (int N,int M, int **arr)
{ HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hStdout, 10);
printf("\n Bistr sort.\n");
SetConsoleTextAttribute(hStdout, 15);
int sravnenii = 0, obmenov = 0;
int mas[100];
int count = 0;
for (int i=0; i<M; ++i)
{
	count=0;
		for (int j=0;j<N;j++)
		{
			if (arr[j][i]%2==0)
			{
				mas[count]=arr[j][i];
				count++;
			}
		}
	quick_sort(mas, 0,count-1, sravnenii, obmenov);
	count=0;
    	for (int j=0;j<N;j++)
		{
			if (arr[j][i]%2==0)
			{
				arr[j][i]=mas[count];
				count++;
			}
		}
}
for (int i=0; i<N; ++i)
{for (int j=0; j<M; ++j)
printf (" %4.1d ", arr[i][j]);
printf ("\n");
}
SetConsoleTextAttribute(hStdout, 23);
printf ("sravneniy: %d,  obmenov: %d.\n", sravnenii, obmenov);
sravnii[4]=sravnenii;
perestanovok[4]=obmenov;}
/////////////////////////////////////////////////Задаем массив////////////////////////////////////////////////////////////////////
void main(int argc, _TCHAR* argv[])
{
	//setlocale (0, "");
	srand (unsigned(time(NULL)));
	int N, M;
	printf ("Enter matrix size: \n");
	printf ("Enter N: ");
	cin >> N;
	printf ("Enter M: ");
	cin >> M;
	int ** arr = new int * [N];
		for (int i=0; i<N; i++)
			arr [i] = new int [M];

		for (int i=0; i<N; i++)
			for (int j=0; j<M; j++)
				arr [i][j] = ((rand()%200-100));
		printf ("------------Matrix------------\n");
		for (int i=0; i<N; i++)
		{
			for (int j=0; j<M; j++)
				printf(" %4.1d ", arr[i][j]);
				printf("\n");
		}
		printf ("\n");
						//for (int i=0; i<N; i++)
							//delete [] Arr[i];
							//delete [] Arr;



	printf("---------------------------------------------------------- \n");

	bubble_sort(N, M, arr);
	select(N,M,arr);
	insert(N, M, arr);
	shell (N,M,arr);
	qs (N,M,arr);
}