VOLKOV CHMA

#include <iostream>

#define MAX_INT (long)pow(2,8*sizeof(int) - 1) - 1	//Максимальное число типа int
#define MIN_INT (long)pow(2,8*sizeof(int) - 1)		//Минимальное число типа int
#define LEN_STRING 1000

int enterInt(int min, int max);
int enterArray();
void quickSort(int* a, int n, int first, int last);
void outputArray(int* a, int n);

int main(int* a, int n)
{
	setlocale(LC_ALL, "Rus");	//Русская раскладка в консоли

	printf("Упорядочивание элементов массива по возрстанию методом быстрой сортировки\n\n");
	enterArray();
	system("PAUSE");
}

int enterArray()	// Ввод массива
{
	int *a;
	int n;

	printf("Введите количество элементов массива:\n");
	n = enterInt(1, LEN_STRING);

	printf("Введите эементы массива:\n");
	a = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		a[i] = enterInt(MIN_INT, MAX_INT);

	printf("Исходный массив:\n");
	outputArray(a, n);
	printf("\n");

	quickSort(a, n, 0, n - 1);

	printf("\nОтсортированный массив:\n");
	outputArray(a, n);
	return 0;
}

int enterInt(int min, int max)	//Проверка вводимого пользователем числа в заданном диапазоне
{
	long int integer;	//Вводимое число типа int

	while (1)
	{
		if (scanf_s("%d", &integer) != 1)	//Проверка на ввод символа
		{
			printf("Неверный ввод! Введите целочсленное число.\n");
			while (getchar() != '\n');
		}
		else
		{
			if ((integer >= min) && (integer <= max))
				return integer;
			else
				printf("Неверный ввод! Введите число в диапазоне от %d до %d.\n", min, max);
		}
	}
}

void quickSort(int* a, int n, int first, int last)	//Метод быстрой сортировки
{
	int l = first, r = last;		//Индекс левой и правой границы сортируемого диапазона
	int mid = (first + last) / 2;	//Индекс среднего значения сортируемого диапазона
	int mid0;	//Значение среднего элемента массива перед началом сортировки
	int temp;

	do
	{
		mid0 = a[mid];
		while (a[mid] > a[l]) l++;
		while (a[r] > a[mid]) r--;
		if (l <= r)
		{
			temp = a[l];
			a[l] = a[r];
			a[r] = temp;
			l++;
			r--;
		}

		if (a[mid] != mid0)	//При смене среднего значения массива, запускаем цикл заного
		{
			l = 0;
			r = n - 1;
		}
	} while (l <= r);

	outputArray(a, n);

	if (l < last) quickSort(a, n, mid + 1, last);
	if (first < r) quickSort(a, n, first, mid - 1);
}

void outputArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
		printf("a[%d]=%d; ", i, a[i]);
	printf("\n");
}