// ConsoleApplication1.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;
struct DATE
{
	double time;
    unsigned int countComprasion=0;
	unsigned int countAssigmant=0;
};
void InitArrayInc(int *temp, int N)
{
	for (int i = 0; i < N; i++)
	{
		temp[i] = i;
	}
}
void InitArrayDec(int *temp, int N)
{
	for (int i = N,j=0; j<N; i--,j++)
	{
		temp[j] = i;
	}
}
void InitArrayRand(int *temp, int N)
{
	for (int i = 0; i < N; i++)
	{
		temp[i] = rand()%1000+1;
	}
}
void BubbleSort(int *tempA, int N, DATE* tempD,int k,double &ref)
{
	int temp;
	for (int i = 0; i < N - 1; i++)
	{
		for (int j = 0; j < (N - 1); j++)
		{
			if (tempA[j] < tempA[j + 1])
			{
				temp = tempA[j];
				tempA[j] = tempA[j + 1];
				tempA[j + 1] = temp;
				tempD[k].countComprasion += 3;
			}
			tempD[k].countAssigmant++;
		}
	}
	ref= (clock() - ref) / 1000.0;
	tempD[k].time = ref;
}
void QuickSort(int *tArray, int first, int last,int L, DATE* tempD, int k,double& ref)
{
	int pivot, temp;
	int i = first, j = last;
	if (L==1)
	{
        pivot = tArray[(i + j) / 2];
	}
	if (L == 2)
	{
		pivot = tArray[j];
	}
	while(i<j)
	{
		while (tArray[i] < pivot)
		{
			i++;
			tempD[k].countComprasion++;
		}
		tempD[k].countComprasion++;
		while (tArray[j] > pivot)
		{
			j--;
			tempD[k].countComprasion++;
		}
		tempD[k].countComprasion++;
		if (i <= j) //перестановка элементов
		{
			temp = tArray[i];
			tArray[i] = tArray[j];
			tArray[j] = temp;
			i++;
			j--;
			tempD[k].countComprasion++;
			tempD[k].countAssigmant += 3;
		}
	}
	if (first<j)
	{
		tempD[k].countComprasion++;
        QuickSort(tArray, first, j,L,tempD,k,ref);
	}
	if (last > i)
	{
		tempD[k].countComprasion++;
		QuickSort(tArray, i, last, L, tempD, k,ref);
	}
tempD[k].time = clock() / 1000.0 - ref;
}
void Print(DATE* tempD,int N)
{
	cout << "Сравнения" << endl;
	for (int i = 0; i < N; i++)
	{
		cout << i+1 << ") ";
		cout << tempD[i].countAssigmant<<"  ";
	}
	cout << endl;
	cout << "Присваивания" << endl;
	for (int i = 0; i < N; i++)
	{
		cout << i + 1 << ") ";
		cout << tempD[i].countComprasion << "  ";
	}
	cout << endl;
	cout << "Время" << endl;
	for (int i = 0; i < N; i++)
	{
		cout << i + 1 << ") ";
		cout << tempD[i].time << "  ";
	}
}
void Clean(DATE* tempD)
{
	for (int i = 0; i < 6; i++)
	{
		tempD[i].countAssigmant = 0;
		tempD[i].countComprasion = 0;
		tempD[i].time = 0;
	}
}
void Print(int* temp,int N)
{
	for (int i = 0; i < N; i++)
	{
		cout << temp[i] << " ";
	}
}
int main()
{
	setlocale(LC_ALL, "RUS");
    const int N = 100, NR1 = 10, NR2 = 1000, NR3 = 10000, NR4 = 100000;
	int arrayIncrease[N], arrayDecrease[N],arrayRandomOne[NR1], arrayRandomTwo[NR2], arrayRandomThree[NR3], arrayRandomFour[NR4];
	double arrayTime[20];
	DATE obj[30];
	double difTime = 0;
	double& refDifT=difTime;

	InitArrayInc(arrayIncrease, N);
	InitArrayDec(arrayDecrease, N);
	InitArrayRand(arrayRandomOne, NR1);
	InitArrayRand(arrayRandomTwo, NR2);
	InitArrayRand(arrayRandomThree, NR3);
	InitArrayRand(arrayRandomFour, NR4);

	srand(time(0));
	refDifT = clock()/1000.0;
	BubbleSort(arrayIncrease, N,obj,0, refDifT);
	BubbleSort(arrayDecrease, N,obj, 1, refDifT);
	BubbleSort(arrayRandomOne,NR1, obj,2, refDifT);
	BubbleSort(arrayRandomTwo,NR2,obj,3, refDifT);
	BubbleSort(arrayRandomThree,NR3,obj,4, refDifT);
	BubbleSort(arrayRandomFour,NR4,obj,5, refDifT);
	cout << "Сортировка пузырьком" << endl;
    Print(obj, 6);
	cout << endl;
	Clean(obj);
	cout << endl;
	QuickSort(arrayIncrease, 0,N-1,1, obj, 0, refDifT);
	QuickSort(arrayDecrease,0, N-1,1, obj, 1, refDifT);
	QuickSort(arrayRandomOne, 0,NR1-1,1, obj, 2, refDifT);
	QuickSort(arrayRandomTwo, 0,NR2-1,1, obj, 3, refDifT);
	QuickSort(arrayRandomThree, 0,NR3-1,1, obj, 4, refDifT);
	QuickSort(arrayRandomFour, 0,NR4-1,1, obj, 5, refDifT);
	cout << "Быстрая сортировка(1)" << endl;
	Print(obj, 6);
	cout << endl;
    Clean(obj);
	QuickSort(arrayIncrease, 0, N - 1, 1, obj, 0, refDifT);
	QuickSort(arrayDecrease, 0, N - 1, 1, obj, 1, refDifT);
	QuickSort(arrayRandomOne, 0, NR1 - 1, 2, obj, 2, refDifT);
	QuickSort(arrayRandomTwo, 0, NR2 - 1, 1, obj, 3, refDifT);
	QuickSort(arrayRandomThree, 0, NR3 - 1, 1, obj, 4, refDifT);
	QuickSort(arrayRandomFour, 0, NR4 - 1, 1, obj, 5, refDifT);
	cout << endl;
	cout << "Быстрая сортировка(2)" << endl;
	Print(obj, 6);
	cout << endl;
	Clean(obj);
	cout << "Проверка пузырька:" << endl;
	InitArrayRand(arrayRandomOne, NR1);
	cout << "До сортировки" << endl;
	Print(arrayRandomOne, NR1);
	cout << endl;
	BubbleSort(arrayRandomOne, NR1, obj, 2, refDifT);
	cout << "После сортировки" << endl;
	Print(arrayRandomOne, NR1);
	cout << endl<<endl;
	cout << "Проверка быстрой сортировки:" << endl;
	InitArrayRand(arrayRandomOne, NR1);
	cout << "До сортировки" << endl;
	Print(arrayRandomOne, NR1);
	cout << endl;
	QuickSort(arrayRandomOne, 0, NR1 - 1, 1, obj, 2, refDifT);
	cout << "После сортировки" << endl;
	Print(arrayRandomOne, NR1);
    return 0;
}