code_Tumanov

#include <stdio.h>
#include <locale.h>
#include <stdlib.h>
#include <windows.h>

void print_menu()
{
	printf("0. Input array \n"); //Ввод массива пользователем +
	printf("1. Generation array \n"); //Генерация рандомного массива +
	printf("2. Bubble Sort \n"); //Сортировка массива пузырьком +
	printf("3. VIP Bubble Sort \n"); //Сортировка массива супер пузырьком (двунаправленный) +
	printf("4. Insert Sort \n"); //Сортировка массива вставкой +
	printf("5. Choice Sort \n"); //Сортировка массива выбором +
	printf("6. Merge Sort \n"); //Сортировка массива слиянием
	printf("7. Counting Sort \n"); //Сортировка массива подсчётом +
	printf("8. Quick Sort \n"); //Сортировка массива Хоара ("быстрая") +
	printf("9. Linear Search \n"); //Линейный поиск +
	printf("10. Binary Search \n"); //Бинарный поиск +
	printf("11. Exit \n"); //Выход из программы
}
//Функция ввода массива пользователем
void Input_array(int A[], int n)
{
	int i;
	printf("Введи массив, состоящий из %d элементов \n", n);
	for (i = 0; i < n; i++)
		scanf_s("%d", &A[i]);
	printf("Вот твой массив \n");
	for (i = 0; i < n; i++)
		printf("%d ", A[i]);
	printf("\n");
}
//Функция копирования массива
void Copy_array(int A[], int B[], int n)
{
	int i;
	for (i = 0; i < n; i++)
		B[i] = A[i];
}
//Функция генерации рандомного массива
void Generation_array(int A[], int n)
{
	int i;
	for (i = 0; i < n; i++)
		A[i] = rand();
	printf("Вот твой сгенерированный массив \n");
	for (i = 0; i < n; i++)
		printf("%d ", A[i]);
	printf("\n");
}
//Функция сортировки массива Пузырьком
void Bubble_Sort(int A[], int n,double Time[],int Swaps[])
{
	int i, j, c,kolic_sravn=0,kolic_perest=0;
	for (i = 0; i < n; i++)
	{
		for (j = i; j < n; j++)
		{
			if (A[i] > A[j])
			{
				c = A[i];
				A[i] = A[j];
				A[j] = c;
				kolic_perest++; //Увеличиваем количество перестановок
			}
			kolic_sravn++; //Увеличиваем количество сравнений
		}
	}
	printf("Bubble Sort \n");
	for (i = 0; i < n; i++)
		printf("%d ", A[i]);
	printf("\n");
	printf("Количество сравнений равно %d \n", kolic_sravn);
	printf("Количество перестановок равно %d \n", kolic_perest);
}
//Функция Сортировки Супер Пузырьком
void VIP_Bubble_Sort(int A[], int n)
{
	int i, j, f = 1, left = 0, right = n, c,kolic_sravn=0,kolic_perest=0;
	for (i = 0; (i < n) && (f); i++)
	{
		f = 0;
		if (i % 2 == 1)
		{
			// =>
			for (j = left; j < right - 1; j++)
			{
				if (A[i] > A[j + 1])
				{
					c = A[j];
					A[j] = A[j + 1];
					A[j + 1] = c;
					f = 1;
					kolic_perest++; //Увеличиваем количество перестановок
				}
				kolic_sravn++; //Увеличиваем количество сравнений
			}
			right--;
		}
		else //i - чётная
		{
			for (j = (right - 1); j > left; j--)
			{
				if (A[j] > A[j - 1])
				{
					c = A[j];
					A[j] = A[j + 1];
					A[j + 1] = c;
					f = 1;
					kolic_perest++; //Увеличиваем количество перестановок
				}
				kolic_sravn++; //Увеличиваем количество сравнений
			}
			left++;
		}
	}
	printf("VIP Bubble Sort \n");
	for (i = 0; i < n; i++)
		printf("%d ", A[i]);
	printf("\n");
	printf("Количество сравнений равно %d \n", kolic_sravn);
	printf("Количество перестановок равно %d \n", kolic_perest);
}
//Функция Сортировки массива Вставкой
void Insert_Sort(int A[], int n,double Time[],int Swaps[])
{
	int pos, val, k, i,kolic_sravn=0,kolic_perest=0;
	for (pos = 1; pos < n; pos++)
	{
		val = A[pos];
		k = pos;
		for (k = pos - 1; ((k >= 0) && (A[k] > val)); k--)
		{
			kolic_sravn++; //Увеличиваем количество сравнений
			A[k + 1] = A[k];//сдвиг
			kolic_perest++; //Увеличиваем количество перестановок
		}
		A[k + 1] = val;
	}
	printf("Insert Sort \n");
	for (i = 0; i < n; i++)
		printf("%d ", A[i]);
	printf("\n");
	printf("Количество сравнений равно %d \n", kolic_sravn);
	printf("Количество перестановок равно %d \n", kolic_perest);
}
//Функция Сортировки массива Выбором
void Choice_Sort(int A[], int n, double Time[], int Swaps[])
{
	int pos, index, index_min, tmp, i, kolic_sravn = 0, kolic_perest = 0;
	for (pos = 0; pos < n; pos++)
	{
		index_min = pos;
		for (index = (pos + 1); index < n; index++)
		{
			if (A[index_min] > A[index])
				index_min = index;
			kolic_sravn++; //Увеличиваем количество сравнений
		}
		tmp = A[index_min];
		A[index_min] = A[pos];
		A[pos] = tmp;
		kolic_perest++; //Увеличиваем количество перестановок
	}
	printf("Choice Sort \n");
	for (i = 0; i < n; i++)
		printf("%d ", A[i]);
	printf("\n");
	printf("Количество сравнений равно %d \n", kolic_sravn);
	printf("Количество перестановок равно %d \n", kolic_perest);
}
//Функция слияния упорядоченных массивов
void merge(int A[], int left, int mid, int right)
{
	int tmp;
	if (A[left] > A[left + 1])
	{
		tmp = A[left];
		A[left] = A[left + 1];
		A[left + 1] = tmp;
	}
}
//Функция Сортировки массива Слиянием
void Merge_Sort(int A[], int left, int right)
{
	int mid = (left + right) / 2;
	if ((mid - 1) > 1)
		Merge_Sort(A, left, mid);
	if ((right - (mid + 1)) > 1)
		Merge_Sort(A, mid + 1, right);
	merge(A, left, mid, right);
	printf("Merge Sort \n");
}
//Функция Сортировки массива Подсчётом
void Counting_Sort(int A[], int n, double Time[], int Swaps[])
{
	int i, j, k, B[1000], c, kolic_sravn = 0, kolic_perest = 0;
	for (c = 0; c < n; c++)
		B[c] = 0;
	for (i = 0; i < n; i++)
	{
		k = 0;
		for (j = 0; j < n; j++)
			if ((j != i) && (A[j] < A[i]))
			{
				kolic_sravn++; //Увеличивааем количество сравнений
				k++;
			}
		B[k] = A[i];
		kolic_perest++; //Увеличиваем количество перестановок
	}
	printf("Counting Sort \n");
	for (c = 0; c < n; c++)
		printf("%d ", B[c]);
	printf("\n");
	printf("Количество сравнений равно %d \n", kolic_sravn);
	printf("Количество перестановок равно %d \n", kolic_perest);
}
//Функция Сортировки массива Хоара ("Быстрая сортировка")
void Quick_Sort(int A[], int left, int right)
{
	int i, j, tmp,kolic_perest=0;
	int mid = (right + left) / 2;
	int val = A[mid];
	if ((mid - left) > 0) Quick_Sort(A, left, mid);
	if ((right - mid) > 0) Quick_Sort(A, mid + 1, right);
	i = left; j = right;
	while (i < j)
	{
		while (A[i] < val) i++;
		while (A[j] > val) j--;
		if (i <= j)
		{
			tmp = A[i];
			A[i] = A[j];
			A[j] = tmp;
			kolic_perest++; //Увеличиваем количество перестановок
			i++; j--;
		}
	}
}
//Функция Линейного поиска
void Linear_Search(int A[], int n)
{
	int val, i, k = -1,kolic_sravn=0;
	printf("Введи значение, которое хочешь найти в массиве \n");
	scanf_s("%d", &val);
	for (i = 0; i < n; i++)
	{
		if (A[i] == val)
		{
			k = i;
			break;
		}
		kolic_sravn++; //Увеличиваем количество сравнений
	}
	if (k > -1)
		printf("Значение, которое вы ищете емеется в массиве и его индекс равен %d \n", k);
	else
		printf("Данного значения нет в массиве \n");
	printf("Количество сравнений равно %d \n", kolic_sravn);
}
//Функция Бинарного поиска
void Binary_Search(int A[], int n)
{
	int left, right, m, val, f = 0,kolic_sravn=0;
	printf("Введи значение, которое хочешь найти в массиве \n");
	scanf_s("%d", &val);
	left = 0;
	right = n - 1;
	while ((left < right) && (!f))
	{
		m = (left + right) / 2;
		if (val > A[m])
		{
			left = m + 1;
			kolic_sravn++; //Увеличиваем количество сравнений на 1 единицу
		}
		else if (val < A[m])
		{
			right = m - 1;
			kolic_sravn++; //Увеличиваем количество сравнений на 2 единицы
		}
		else
		{
			f = 1;
			kolic_sravn++; //Увеличиваем количество сравнений на 2 единицы
		}
	}
	if (f)
		printf("Элемент найден и его индекс равен %d \n", m);
	else
		printf("Элемент не найден \n");
	printf("Количество сравнений равно %d \n", kolic_sravn);
}
//Главная программа
int main()
{
	int c = 1;
	int n;
	int A[100];
	int Acopy[100];
	double Time[7];
	int SwapCount[7];
	int status = 0;
	LARGE_INTEGER freq, start, finish;
	double time;

	QueryPerformanceFrequency(&freq);

	setlocale(LC_ALL, "Russian");
	while (c != 11)
	{
		print_menu();
		scanf_s("%d", &c);
		//Copy_array(A, Acopy, n);
		switch (c)
		{
		case 0:
			printf("Введи количество элементов в массиве \n");
			scanf_s("%d", &n);
			Input_array(A, n);
			status = 1;
			break;
		case 1:
			printf("Введи количество элементов в массиве \n");
			scanf_s("%d", &n);
			Generation_array(A, n);
			status = 1;
			break;
		case 2:
			if (status > 0)
			{
				Copy_array(A, Acopy, n); //Копирование массива
				QueryPerformanceCounter(&start);
				Bubble_Sort(Acopy, n,Time,SwapCount);
				QueryPerformanceCounter(&finish);
				time = (double)(finish.QuadPart -
					start.QuadPart) / (double)freq.QuadPart;
				status = 2;
				Time[0] = time;
				printf("Bubble_Sort time = %.5f\n", Time[0]);
			}
			else printf("Input array or Generation array \n"); break;
		case 3:
			if (status > 0)
			{
				Copy_array(A, Acopy, n); //Копирование массива
				VIP_Bubble_Sort(Acopy, n);
				status = 2;
			}
			else printf("Input array or Generation array \n"); break;
		case 4:
			if (status > 0)
			{
				Copy_array(A, Acopy, n); //Копирование массива
				QueryPerformanceCounter(&start);
				Insert_Sort(Acopy, n,Time,SwapCount);
				QueryPerformanceCounter(&finish);
				time = (double)(finish.QuadPart -
					start.QuadPart) / (double)freq.QuadPart;
				status = 2;
				Time[1] = time;
				printf("Insert_Sort time = %.5f\n", Time[1]);
			}
			else printf("Input array or Generation array \n"); break;
		case 5:
			if (status > 0)
			{
				Copy_array(A, Acopy, n); //Копирование массива
				QueryPerformanceCounter(&start);
				Choice_Sort(Acopy, n, Time, SwapCount);
				QueryPerformanceCounter(&finish);
				time = (double)(finish.QuadPart -
					start.QuadPart) / (double)freq.QuadPart;
				status = 2;
				Time[2] = time;
				printf("Choice_Sort time = %.5f\n", Time[2]);
			}
			else printf("Input array or Generation array \n"); break;
		case 6:
			if (status > 0)
			{
				int i;
				Copy_array(A, Acopy, n); //Копирование массива
				Merge_Sort(Acopy, 0, (n - 1));
				for (i = 0; i < n; i++)
					printf("%d ", Acopy[i]);
				printf("\n");
				status = 2;
			}
			else printf("Input array or Generation array \n"); break;
		case 7:
			if (status > 0)
			{
				Copy_array(A, Acopy, n); //Копирование массива
				QueryPerformanceCounter(&start);
				Counting_Sort(Acopy, n,Time,SwapCount);
				QueryPerformanceCounter(&finish);
				time = (double)(finish.QuadPart -
					start.QuadPart) / (double)freq.QuadPart;
				status = 2;
				Time[3] = time;
				printf("Counting_Sort time = %.5f\n", Time[3]);
			}
			else printf("Input array or Generation array \n"); break;
		case 8:
			if (status > 0)
			{
				int i;
				Copy_array(A, Acopy, n); //Копирование массива
				//QueryPerformanceCounter(&start);
				Quick_Sort(Acopy, 0, (n - 1));
				//QueryPerformanceCounter(&finish);
				//time = (double)(finish.QuadPart -
					//start.QuadPart) / (double)freq.QuadPart;
				printf("Quick Sort \n");
				for (i = 0; i < n; i++)
					printf("%d ", Acopy[i]);
				printf("\n");
				status = 2;
				//Time[4] = time;
				//printf("Quick_Sort time = %.5f\n", Time[4]);
			}
			else printf("Input array or Generation array \n"); break;
		case 9:
			if (status > 0)
			{
				Copy_array(A, Acopy, n); //Копирование массива
				Linear_Search(Acopy, n);
				status = 2;
			}
			else printf("Input array or Generation array \n"); break;
		case 10:
			if (status > 1)
			{
				Copy_array(Acopy, Acopy, n); //Копирование массива
				Binary_Search(Acopy, n);
				status = 2;
			}
			else if (status = 0)
				printf("Input array or Generation array \n");
			else if (status = 1)
				printf("Sort the array!!! \n");
		}
	}
}