#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <locale.h>

int selectionSort(int *arr, int size) /// Функция сортировки прямым выбором
{
	int min, temp; // для поиска минимального элемента и для обмена
	for (int i = 0; i < size - 1; i++)
	{
		min = i; // запоминаем индекс текущего элемента
		// ищем минимальный элемент чтобы поместить на место i-ого
		for (int j = i + 1; j < size; j++)  // для остальных элементов после i-ого
		{
			if (arr[j] < arr[min]) // если элемент меньше минимального,
				min = j;       // запоминаем его индекс в min
		}
		temp = arr[i];      // меняем местами i-ый и минимальный элементы
		arr[i] = arr[min];
		arr[min] = temp;	}
	return *arr;
}



void mergeSort(int *a, int l, int r)
{
	if (l == r) return; // границы сомкнулись
	int mid = (l + r) / 2; // определяем середину последовательности
	// и рекурсивно вызываем функцию сортировки для каждой половины
	mergeSort(a, l, mid);
	mergeSort(a, mid + 1, r);

	int i = l; // начало первого пути
	int j = mid + 1; // начало второго пути
	int *tmp = (int*)malloc(r * sizeof(int)); // дополнительный массив
	for (int step = 0; step < r - l + 1; step++) // для всех элементов дополнительного массива
	{
		// записываем в формируемую последовательность меньший из элементов двух путей
		// или остаток первого пути если j > r
		if ((j > r) || ((i <= mid) && (a[i] < a[j])))
		{
			tmp[step] = a[i];
			i++;
		}
		else
		{
			tmp[step] = a[j];
			j++;
		}
	}
	// переписываем сформированную последовательность в исходный массив
	for (int step = 0; step < r - l + 1; step++)
		a[l + step] = tmp[step];
}

void main() {
	float start1, start2, stop1, stop2;
	int *arr, *arr1, size;
	scanf_s("%d", &size);
	setlocale(LC_ALL, "Rus");

	arr = (int*)calloc(size, sizeof(int));
	srand(time(NULL));
	for (int i = 0; i < size; i++) {
		arr[i] = -50 + rand() % (101);
		printf("%d ", arr[i]);
	}
	arr1 = (int*)calloc(size, sizeof(int));
	printf("\n");
	for (int i = 0; i < size; i++) {
		arr1[i] = arr[i];
	}
	start1 = clock();
	selectionSort(arr, size);
	stop1 = clock();
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	start2 = clock();
	mergeSort(arr1, 0, size - 1); // вызываем функцию сортировки
	stop2 = clock();
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr1[i]);
	}

	printf("\n Время сортировки прямым выбором : %f\n", (stop1 - start1) / CLOCKS_PER_SEC);
	printf("\n Время сортировки слиянием: %f\n", (stop2 - start2) / CLOCKS_PER_SEC);

	getchar();
	getchar();
	free(arr);
}