---

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

const int N = 10000;

void best_case(int* array, int n)
{
	// TODO функция заполняет массив array размером n элементами в прямом порядке (по возрастанию)
	for (int i = 0; i < n; i++) {
		array[i] = i + 1;
	}
	return;
}

void worst_case(int* array, int n)
{
	// TODO функция заполняет массив array размером n элементами в обратном порядке (по убыванию)
	for (int i = n-1; i >= 0; i--) {
		array[i] = n - i;
	}
	return;
}

void average_case(int* array, int n)
{
	// TODO функция заполняет массив array размером n элементами в случайном порядке (с использованием функции rand)
	for (int i = 0; i < n; i++) {
		array[i] = rand();
	}
	return;
}

unsigned long long bubble_sort(int* a, int n)
{
	unsigned long long op_counter = 0;
	// TODO функция реализует сортировку пузырьком массива a размером n по возрастанию 
	// функция возвращает количество операций сравнения элементов - op_counter
	int temp;
	for (int i = 0; i < n-1; i++) {
		for (int j = 0; j < n - 1 - i; j++) {
			op_counter++;
			if (a[j] > a[j + 1]) {
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
	return op_counter;
}

unsigned long long bubble_sort_opimized(int* a, int n)
{
	unsigned long long op_counter = 0;
	bool swapped = false;
	int temp;
	// TODO функция реализует оптимизированную сортировку пузырьком массива a размером n по возрастанию 
	// функция возвращает количество операций сравнения элементов - op_counter
	for (int i = 0; i < n - 1 && !swapped; i++) {
		swapped = true;
		for (int j = 0; j < n - 1 - i; j++, op_counter++) {
			if (a[j] > a[j + 1]) {
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
				swapped = false;
			}
		}
	}
	return op_counter;
}

unsigned long long comb_sort(int* a, int n)
{
	unsigned long long op_counter = 0;
	// TODO функция реализует сортировку расческой массива a размером n по возрастанию 
	// функция возвращает количество операций сравнения элементов - op_counter
	int gap = n, temp;
	bool sorted = true;
	while (gap > 1 || sorted) {
		gap = static_cast<int>(gap / 1.247330950103979);
		if (gap < 1) {
			gap = 1;
		}
		sorted = false;
		for (int i = 0; i + gap < n; i++) {
			op_counter++;
			if (a[i] > a[i + gap]) {
				temp = a[i];
				a[i] = a[i + gap];
				a[i + gap] = temp;
				sorted = true;
			}
		}
		
	}
	return op_counter;
}


// Функция копирует массив arr2 размером n в arr1
void copy_array(int* arr1, int* arr2, int n)
{
	for (int i = 0; i < n; i++)
	{
		arr1[i] = arr2[i];
	}
}

// Функция проверяет, отсортирован ли массив, чтобы проверить, что сортировки работают :)
void is_sorted(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		if (arr[i] > arr[i + 1])
			throw runtime_error("Array is not sorted!");
	}
}

// Функция добавляет новую строку к файлу таблицы
// sums - массив из 3 чисел, содержащих количество операций сравнения в алгоритмах сортировки: 
// 1) пузрьком 2) оптимизированным пузырьком 3) расческой 
// n - количество элементов в сортируемых массивах
// type - одна из строк "best", "worst", "average" - прямой, обратный, случайный порядок следования элементов
// file - поток, в который записываются значение type, n, sums - т.е. файл таблицы
void add_to_file(unsigned long long* sums, int n, string type, ofstream& file)
{
	file << type << ";" << n << ";";
	for (int k = 0; k < 3; k++)
		file << sums[k] << ";";
	file << "\n";
}

int main()
{
	ofstream file("results.csv"); // создание файла таблицы
	file << "type;size;bubble;optimized_bubble;comb\n"; // создание первой строки в таблице

	// исследуемые размеры массивов для сортировки
	int array_lengths[] = { 4, 8, 16, 32, 64, 128, 256, 512, 1024 }; // Вы можете добавить другие размеры массивов

	for (int i = 0; i < 9; i++) // это цикл по array_lengths
	{
		int n = array_lengths[i]; // n - размер массива, элемент array_lengths 
		// выделяем память на массивы из 4, 8, 64,.. элементов
		// один массив = один алгоритм сортировки
		int* arr = new int[n]; // пузырек
		int* arr2 = new int[n]; // оптимизированный пузырек
		int* arr3 = new int[n]; // расческа 

		unsigned long long sums[3] = { 0 }; // массив, содержащий количество операций сортировки 1) пузырьком 2) оптимизированным пузырьком, 3) расческой

		// Случайный порядок следования элементов:
		for (int j = 0; j < N; j++)
		{
			// TODO сгенерировать случайную последовательность в массив arr
			// TODO скопировать ее в массив arr2
			// TODO скопировать ее в массив arr3
			average_case(arr, n);
			copy_array(arr2, arr, n);
			copy_array(arr3, arr, n);

			// TODO в соответствующем элементе sum накапливаем количество операций для каждой сортировки
			sums[0] += bubble_sort(arr, n);
			sums[1] += bubble_sort_opimized(arr2, n);
			sums[2] += comb_sort(arr3, n);

			// проверка на корректность алгоритма:
			is_sorted(arr, n);
			is_sorted(arr2, n);
			is_sorted(arr3, n);
		}

		// TODO каждый элемент sums нужно усреднить
		sums[0] /= N;
		sums[1] /= N;
		sums[2] /= N;

		add_to_file(sums, n, "average", file); // результаты записываются в файл


		// Прямой порядок следования элементов
		// TODO сгенерировать возрастающую последовательность в массив arr
		// 
		// TODO скопировать ее в массив arr2
		// TODO скопировать ее в массив arr3
		best_case(arr, n);
		for (int u = 0; u < n; u++) {
			arr2[u] = arr[u];
			arr3[u] = arr[u];
		}
		// TODO в соответствующий элемент sum записать количество операций сравнения для каждой сортировки
		sums[0] = bubble_sort(arr, n);
		sums[1] = bubble_sort_opimized(arr2, n);
		sums[2] = comb_sort(arr3, n);
		// проверка на корректность алгоритма:
		is_sorted(arr, n);
		is_sorted(arr2, n);
		is_sorted(arr3, n);

		add_to_file(sums, n, "best", file); // результаты записываются в файл



		// Обратный порядок следования элементов
		// TODO сгенерировать убывающую последовательность в массив arr
		// TODO скопировать ее в массив arr2
		// TODO скопировать ее в массив arr3 
		worst_case(arr, n);
		for (int u = 0; u < n; u++) {
			arr2[u] = arr[u];
			arr3[u] = arr[u];
		}
		// TODO в соответствующий элемент sum записать количество операций сравнения для каждой сортировки
		sums[0] = bubble_sort(arr, n);
		sums[1] = bubble_sort_opimized(arr2, n);
		sums[2] = comb_sort(arr3, n);
		// проверка на корректность алгоритма:
		is_sorted(arr, n);
		is_sorted(arr2, n);
		is_sorted(arr3, n);

		add_to_file(sums, n, "worst", file); // результаты записываются в файл

		// освобождение памяти массивов
		delete[] arr;
		delete[] arr2;
		delete[] arr3;
	}

	file.close(); //закрытие файла
}