lab4 task1

#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");
}