#include "stdafx.h"
#include "math.h"
#include <iostream>
#include <time.h>
#include <windows.h>
#include <stdio.h>
#include <conio.h>
#include <iomanip>

using namespace std;
unsigned int stime = (unsigned) time(NULL)/2;
srand(stime);
//Пузырек

void bubblesort1(int * a, int n,int data[][2])
{
  int i, j;
  int lasts=n;
  for (i = lasts - 1; i > 0; i--)
  {
    lasts=0;
    for (j = 0; j < i; j++)
    {
	  data[0][0]++;
      if (a[j] > a[j + 1])
	  {
		data[0][1]++;
        swap( a[j], a[j + 1] );
		lasts=j+1;
	  }
    }
	i=lasts;
  }
}

void bubblesort2(int ** a, int n,int m,int data[][2])
{
  int i, j;
  int lasts=m;
  for (i = lasts - 1; i > 0; i--)
  {
    lasts=0;
    for (j = 0; j < i; j++)
    {
	  data[0][0]++;
      if (a[j][n] > a[j + 1][n])
	  {
		data[0][1]++;
        swap( a[j][n], a[j + 1][n]);
		lasts=j+1;
	  }
    }
	i=lasts;
  }
}
//вставки
void insert1(int * arr,int n,int data[][2])
{
	int temp,j;
	for (int i = 1; i < n; i++)
	{
        temp = arr[i];
        for ( j = i - 1; j >= 0; j--)
		{
				data[1][0]++;
                if (arr[j] <= temp) {
                        break;
                }
                arr[j+1] = arr[j];
        }
		if(i!=j+1)
		{
			arr[j+1] = temp;
			data[1][1]++;
		}
	}
}


void insert2(int** arr,int n,int m,int data[][2])
{
	int temp,j;
	for (int i = 1; i < m; i++)
	{
        temp = arr[i][n];
        for ( j = i - 1; j >= 0; j--)
		{
				data[1][0]++;
                if (arr[j][n] <=temp) {
                        break;
                }
                arr[j+1][n] = arr[j][n];
        }
		if(i!=j+1)
		{
			arr[j+1][n] = temp;
			data[1][1]++;
		}
	}
}
//Шелл
void shell1(int *arr, int n,int data[][2])
{

  register int i, j, gap, k;
  char x, a[5];

  a[0]=9; a[1]=5; a[2]=3; a[3]=2; a[4]=1;

  for(k=0; k < 5; k++) {
    gap = a[k];
    for(i=gap; i < n; ++i) {
      x = arr[i];
	  data[2][0]++;
      for(j=i-gap; (j >= 0)&&(x < arr[j]) ; j=j-gap)
	  {
	    data[2][0]++;
        arr[j+gap] = arr[j];
	  }
	  if(i!=j+gap)
	  {
		data[2][1]++;
		arr[j+gap] = x;
	  }
    }
  }
}

void shell2(int **arr, int n,int m,int data[][2])
{

  register int i, j, gap, k;
  char x, a[5];

  a[0]=9; a[1]=5; a[2]=3; a[3]=2; a[4]=1;

  for(k=0; k < 5; k++)
  {
    gap = a[k];
    for(i=gap; i < m; ++i)
	{
      x = arr[i][n];
	  data[2][0]++;
      for(j=i-gap; (j >= 0)&&(x <arr[j][n]) ; j=j-gap)
	  {
	    data[2][0]++;
        arr[j+gap][n] = arr[j][n];
	  }
	  if(j+gap!=i)
	  {
		data[2][1]++;
		arr[j+gap][n] = x;
	  }
    }
  }
}

//Выбором
void choose1(int* arr,int n,int data[][2])
{
for (int i = 0; i < n - 1; ++i) {
        int min_i = i;
        for (int j = i + 1; j < n; ++j) {
                if (arr[j] < arr[min_i]) {
                        min_i = j;
                }
				data[3][0]++;
        }
		if(i!=min_i)
		{
			swap(arr[i],arr[min_i]);
			data[3][1]++;
		}
}
}

void choose2(int **arr,int n,int m,int data[][2])
{
for (int i = 0; i < m - 1; ++i) {
        int min_i = i;
        for (int j = i + 1; j < m; ++j) {
                if (arr[j][n] < arr[min_i][n]) {
                        min_i = j;
                }
				data[3][0]++;
        }
		if(i!=min_i)
		{
	        swap(arr[i][n],arr[min_i][n]);
			data[3][1]++;
		}
}
}

//быстрая
void qs1(int* arr,int first, int last,int data[][2])
{
    int i = first, j = last, x = arr[(first + last) / 2];

    do {
		while (arr[i] < x)
		{
			i++;
			data[4][0]++;
		}
        while (arr[j] > x)
		{
			data[4][0]++;
			j--;
		}

        if(i <= j) {
            if (i < j)
			{
				if(arr[i]!=arr[j])
				{
					swap(arr[i], arr[j]);
					data[4][1]++;
				}
			}
            i++;
            j--;
        }
    } while (i <= j);

    if (i < last)
        qs1(arr, i, last,data);
    if (first < j)
        qs1(arr, first,j,data);
}

void qs2(int **arr,int n,int first, int last,int data[][2])
{
    int i = first, j = last, x = arr[(first + last) / 2][n];

    do {
		while (arr[i][n] < x)
		{
			i++;
			data[4][0]++;
		}
        while (arr[j][n] > x)
		{
			data[4][0]++;
			j--;
		}

        if(i <= j) {
            if (i < j)
			{
				if(arr[i][n]!=arr[j][n])
				{
					swap(arr[i][n], arr[j][n]);
					data[4][1]++;
				}
			}
            i++;
            j--;
        }
    } while (i <= j);

    if (i < last)
        qs2(arr,n, i, last,data);
    if (first < j)
        qs2(arr,n, first,j,data);
}




void main(int argc, _TCHAR* argv[])
 {
	int M,N;
	cout<<"Inp M\n";
	cin>>M;
	cout<<"Inp N\n";
	cin>>N;
	int **arr=new int* [M];
	int **sorta=new int* [M];
	int data[5][2];
	for(int i=0;i<5;i++)
	{
		data[i][0]=0;
		data[i][1]=0;
	}
	for(int i=0;i<M;i++)
	{
		arr[i]=new int [N];
		sorta[i]=new int [N];
		for(int j=0;j<N;j++)
		{
			arr[i][j]=rand()%10;//20;
			sorta[i][j]=arr[i][j];
		}
	}

	for(int i=0;i<M;i++)
	{
		for(int j=0;j<N;j++)
			cout<<sorta[i][j]<<" ";
		cout<<"\n";
	}
	cout<<"\n";
	int delta;
	bool quit=false;
	//-----------------------------------------------------------------
	while(!quit)
	{
		for(int i=0;i<M;i+=2)
		{
			bubblesort1(sorta[i],N,data);
		}
		delta=data[0][1];

		for(int i=1;i<N;i+=2)
		{
			bubblesort2(sorta,i,M,data);
		}
		if(delta==data[0][1])
			quit=true;
	}
	cout<<"Buble sort\n";
	for(int i=0;i<M;i++)
	{
		for(int j=0;j<N;j++)
			cout<<sorta[i][j]<<" ";
		cout<<"\n";
	}

	//--------------------------------------------------------------------------

	for(int i=0;i<M;i++)
	{
		for(int j=0;j<N;j++)
		{
			sorta[i][j]=arr[i][j];
		}
	}

	quit=false;
	while(!quit)
	{
		for(int i=0;i<M;i+=2)
		{
			insert1(sorta[i],N,data);
		}
		delta=data[1][1];
		for(int i=1;i<N;i+=2)
		{
			insert2(sorta,i,M,data);
		}
		if(delta==data[1][1])
			quit=true;
	}
	cout<<"Insert sort\n";
	for(int i=0;i<M;i++)
	{
		for(int j=0;j<N;j++)
			cout<<sorta[i][j]<<" ";
		cout<<"\n";
	}
	//-------------------------------------------------------------------------
	for(int i=0;i<M;i++)
	{
		for(int j=0;j<N;j++)
		{
			sorta[i][j]=arr[i][j];
		}
	}
	quit=false;
	while(!quit)
	{
		for(int i=0;i<M;i+=2)
		{
			shell1(sorta[i],N,data);
		}
		delta=data[2][1];
		for(int i=1;i<N;i+=2)
		{
			shell2(sorta,i,M,data);
		}
		if(delta==data[2][1])
			quit=true;
	}
	cout<<"shell sort\n";
	for(int i=0;i<M;i++)
	{
		for(int j=0;j<N;j++)
			cout<<sorta[i][j]<<" ";
		cout<<"\n";
	}
	//-------------------------------------------------------------------------
	for(int i=0;i<M;i++)
	{
		for(int j=0;j<N;j++)
		{
			sorta[i][j]=arr[i][j];
		}
	}
	quit=false;
	while(!quit)
	{
		for(int i=0;i<M;i+=2)
		{
			choose1(sorta[i],N,data);
		}
		delta=data[3][1];
		for(int i=1;i<N;i+=2)
		{
			choose2(sorta,i,M,data);
		}
		if(delta==data[3][1])
			quit=true;
	}

	cout<<"Choose sort\n";
	for(int i=0;i<M;i++)
	{
		for(int j=0;j<N;j++)
			cout<<sorta[i][j]<<" ";
		cout<<"\n";
	}
	//-------------------------------------------------------------------------
	for(int i=0;i<M;i++)
	{
		for(int j=0;j<N;j++)
		{
			sorta[i][j]=arr[i][j];
		}
	}
	quit=false;
	while(!quit)
	{
		for(int i=0;i<M;i+=2)
		{
			qs1(sorta[i],0,N-1,data);
		}
		delta=data[4][1];
		for(int i=1;i<N;i+=2)
		{
			qs2(sorta,i,0,M-1,data);
		}
		if(delta==data[4][1])
			quit=true;
	}

	cout<<"Quick sort\n";
	for(int i=0;i<M;i++)
	{
		for(int j=0;j<N;j++)
			cout<<sorta[i][j]<<" ";
		cout<<"\n";
	}
	//-------------------------------------------------------------------------
	cout<<"Param    | Bubble  Insert  Shell  Choose    Quick\n";
	cout<<"Compare  | ";
	for(int i=0;i<5;i++)
	{
		cout<<setw(4)<<data[i][0]<<"    ";
	}
	cout<<"\nSwap     | ";
	for(int i=0;i<5;i++)
	{
		cout<<setw(4)<<data[i][1]<<"    ";
	}
	cout<<"\n";


	system("pause");
}