#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <locale.h>
#define N 10
void quicksort(int a[], int low, int high);
int split(int a[], int low, int high);
void fill_array_random(int a[], int size);
void fill_array_user(int a[], int size);
void print_array(int a[], int size);
// --- Головна програма ---
int main() {
setlocale(LC_ALL, "ukr");
int a[N];
int choice;
printf("Сортування масиву за спаданням (QuickSort)\n");
printf("Оберіть спосіб заповнення масиву:\n");
printf("1 — випадкові числа\n");
printf("2 — введення з клавіатури\n");
printf("Ваш вибір: ");
while (scanf("%d", &choice) != 1 || (choice != 1 && choice != 2)) {
printf("Помилка! Введіть 1 або 2: ");
while (getchar() != '\n');
}
if (choice == 1) {
printf("\nМасив із випадковими числами:\n");
fill_array_random(a, N);
} else {
printf("\nВведіть %d чисел:\n", N);
fill_array_user(a, N);
}
printf("Початковий масив:\n");
print_array(a, N);
quicksort(a, 0, N - 1);
printf("Відсортований масив (за спаданням):\n");
print_array(a, N);
return 0;
}
// --- Швидке сортування ---
void quicksort(int a[], int low, int high) {
int middle;
if (low >= high) return;
middle = split(a, low, high);
quicksort(a, low, middle - 1);
quicksort(a, middle + 1, high);
}
// --- Розділення для сортування за спаданням ---
int split(int a[], int low, int high) {
int part_element = a[low];
for (;;) {
while (low < high && part_element >= a[high])
high--;
if (low >= high) break;
a[low++] = a[high];
while (low < high && a[low] >= part_element)
low++;
if (low >= high) break;
a[high--] = a[low];
}
a[high] = part_element;
return high;
}
// --- Заповнення випадковими числами ---
void fill_array_random(int a[], int size) {
srand((unsigned)time(NULL));
for (int i = 0; i < size; i++) {
a[i] = rand() % 100; // числа від 0 до 99
}
}
// --- Заповнення користувачем ---
void fill_array_user(int a[], int size) {
for (int i = 0; i < size; i++) {
printf("a[%d] = ", i);
while (scanf("%d", &a[i]) != 1) {
printf("Помилка! Введіть ціле число: ");
while (getchar() != '\n'); // очистка буфера
}
}
}
// --- Виведення масиву ---
void print_array(int a[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", a[i]);
}
printf("\n");
}
