/**
* @file lab4.1.cpp
*@author Ткаченко Є.С., гр. 515і
*@date 7 квітня 2023
*@brief Лабораторна робота № 4, варіант 7
*
* Завдання 1. Функції. Швидке сортування. Робота з відлагоджувачем.
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <locale.h>
// заповнення масиву випадковими числами
void ArrayRandom(int arr[], int size) {
srand(time(NULL));
for (int i = 0; i < size; i++) {
arr[i] = rand() % 100;
}
}
// заповнення масиву значеннями, введеними користувачем
void ArrayUser(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("Введiть елемент %d: ", i + 1);
scanf("%d", &arr[i]);
}
}
// Вибір способу заповнення
void ChoiceArray(int arr[], int size) {
int choice;
printf("Оберiть 1 якщо випадкове заповнення\n");
printf("Оберiть 2 якщо ввести з клавiатури\n");
scanf("%d", &choice);
if (choice == 1) {
ArrayRandom(arr, size);
}
else if (choice == 2) {
ArrayUser(arr, size);
}
else {
printf("Помилка!\n");
}
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
// знаходження підмасиву з елементами меншими та більшими опорного елемента
int x = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= x) {
i++;
int temp = arr[i];
arr[i] = arr[j];
// обмін елементів
arr[j] = temp;
}
}
// переміщення опорного елемента на його правильне місце відносно підмасивів з меншими та більшими елементами
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
// рекурсивне сортування лівого та правого підмасивів
quickSort(arr, low, i);
quickSort(arr, i + 2, high);
}
}
// виведення масиву на екран
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
//Головна функція
int main() {
setlocale(LC_ALL, "Ukr");
int size;
printf("Введiть розмiр масиву: ");
scanf("%d", &size);
int arr[100];
ChoiceArray(arr, size);
printf("Масив до сортування: ");
printArray(arr, size);
quickSort(arr, 0, size - 1);
printf("Масив пiсля сортування: ");
printArray(arr, size);
return 0;
}
