// pract3.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
//

#include "pch.h"
#include <iostream>
#include <ctime>
#include <time.h>

using namespace std;

unsigned int inclusionSort(int* const &num, int size) //сортировка включением
{
	unsigned int start_time = clock();
	for (int i = 1; i < size; i++)
	{
		int value = num[i];
		int index = i;
		while ((index > 0) && (num[index - 1] > value))
		{
			num[index] = num[index - 1];
			index--;
		}
		num[index] = value;
	}
	unsigned int end_time = clock();
	return end_time - start_time;
}

unsigned int selectionSort(int* const &num, int size) //сортировка выбором
{
	unsigned int start_time = clock();
	int min, temp;
	for (int i = 0; i < size - 1; i++)
	{
		min = i;
		for (int j = i + 1; j < size; j++)
		{
			if (num[j] < num[min])
				min = j;
		}
		temp = num[i];
		num[i] = num[min];
		num[min] = temp;
	}
	unsigned int end_time = clock();
	return end_time - start_time;
}

unsigned int bubbleSort(int* const &num, int size) //сортировка обменом
{
	unsigned int start_time = clock();
	for (int i = 0; i < size - 1; i++)
	{
		for (int j = (size - 1); j > i; j--)
		{
			if (num[j - 1] > num[j])
			{
				int temp = num[j - 1];
				num[j - 1] = num[j];
				num[j] = temp;
			}
		}
	}
	unsigned int end_time = clock();
	return end_time - start_time;
}

int shekerSort(int* const &num, int count)
{
	int permutations = 0;
	int left = 0, right = count - 1;
	int flag = 1;
	while ((left < right) && flag > 0)
	{
		flag = 0;
		for (int i = left; i < right; i++)
		{
			if (num[i] > num[i + 1])
			{
				int t = num[i];
				num[i] = num[i + 1];
				num[i + 1] = t;
				flag = 1;
				permutations++;
			}
		}
		right--;
		for (int i = right; i > left; i--)
		{
			if (num[i - 1] > num[i])
			{
				int t = num[i];
				num[i] = num[i - 1];
				num[i - 1] = t;
				flag = 1;
				permutations++;
			}
		}
		left++;
	}
	return permutations;
}

int shellSort(int* const &num, int size)
{
	int permutations = 0;
	int increment = 3;
	while (increment > 0)
	{
		for (int i = 0; i < size; i++)
		{
			int j = i;
			int temp = num[i];

			while ((j >= increment) && (num[j - increment] > temp))
			{
				num[j] = num[j - increment];
				j = j - increment;
			}
			num[j] = temp;
			permutations++;
		}
		if (increment > 1)
			increment = increment / 2;
		else if (increment == 1)
			break;
	}
	return permutations;
}

int main()
{
	setlocale(LC_ALL, "RUS");
	int size = 35;
	int* num = new int[size];
	srand((unsigned)time(NULL));
	cout << "Дан массив: " << endl;
	for (int i = 0; i < size; i++)
	{
		num[i] = -100 + rand() % 200;
		cout << num[i] << " ";
	}
	cout << endl;
	cout << endl;
	cout << "Сортировка прямым включением\tвремя\t" << inclusionSort(num, size) << endl;
	cout << "Сортировка прямым выбором\tвремя\t" << selectionSort(num, size) << endl;
	cout << "Сортировка прямым обменом\tвремя\t" << bubbleSort(num, size) << endl;
	cout << endl;
	cout << "Сортировка методом Шейкера\tколичество перестановок\t" << shekerSort(num, size) << endl;
	cout << "Сортировка методом Шелла\tколичество перестановок\t" << shellSort(num, size) << endl;
	cout << endl;
	system("pause");
}