3_task_3_2/task_3_2.cpp - master - khazov/module2

3_task_3_2/task_3_2.cpp
93 строки2 KB
KhazovAV
добавлены задачи по поиску и сортировке
06 авг 2026, 14:16
06 авг 2026, 14:16b97dda2

#include <Windows.h>
#include <iostream>

using namespace std;

// Вспомогательная функция для разбиения массива (partition)
int partition(int* arr, int low, int high)
{
	int pivot = arr[high]; // Опорный элемент — последний
	int i = low - 1; // Индекс меньшего элемента

	for (int j = low; j < high; ++j)
	{
		if (arr[j] <= pivot) { // Если текущий элемент <= опорного
			++i;
			swap(arr[i], arr[j]); // Меняем местами
		}
	}
	swap(arr[i + 1], arr[high]); // Ставим опорный элемент на правильное место
	return i + 1;
}

// Рекурсивная функция быстрой сортировки
void quick_sort_recursive(int* arr, int low, int high)
{
	if (low < high)
	{
		int p = partition(arr, low, high);
		quick_sort_recursive(arr, low, p - 1);
		quick_sort_recursive(arr, p + 1, high);
	}
}

// Функция с требуемой сигнатурой
void quick_sort(int* arr, int size)
{
	if (size <= 1)
		return;
	quick_sort_recursive(arr, 0, size - 1);
}

// Функция для вывода массива
void print_array(const int* arr, int size)
{
	for (int i = 0; i < size; ++i)
	{
		cout << arr[i];
		if (i < size - 1)
			cout << " ";
	}
	cout << endl;
}

int main()
{
	SetConsoleCP(1251);
	SetConsoleOutputCP(1251);

	// Тестовые массивы
	int arr1[] = { 3, 43, 38, 29, 18, 72, 57, 61, 2, 33 };
	int size1 = sizeof(arr1) / sizeof(arr1[0]);

	int arr2[] = { 88, 91, 87, 59, 53, 49, 29, 16, 4, 27, 28, 89, 2, 25, 74 };
	int size2 = sizeof(arr2) / sizeof(arr2[0]);

	int arr3[] = { 24, 66, 20, 79, 30, 16, 19, 62, 94, 59, 0, 7, 59, 90, 84, 60, 95, 62 };
	int size3 = sizeof(arr3) / sizeof(arr3[0]);

	// Тест 1
	cout << "Исходный массив: ";
	print_array(arr1, size1);
	quick_sort(arr1, size1);
	cout << "Отсортированный массив: ";
	print_array(arr1, size1);
	cout << endl;

	// Тест 2
	cout << "Исходный массив: ";
	print_array(arr2, size2);
	quick_sort(arr2, size2);
	cout << "Отсортированный массив: ";
	print_array(arr2, size2);
	cout << endl;

	// Тест 3
	cout << "Исходный массив: ";
	print_array(arr3, size3);
	quick_sort(arr3, size3);
	cout << "Отсортированный массив: ";
	print_array(arr3, size3);

	return EXIT_SUCCESS;
}