/*
* @file lab4_1.c
* @author Герасимюк Д.В., гр. 515і1
* @date 07 квітня 2024
* @brief Лабораторна робота №4, варіант 3
* Функції. Швидке сортування. Робота з відлагоджувачем. Завдання 1
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <locale.h>
#include "sort.h"
#define N 10
int main() {
setlocale(LC_ALL, "Ukr");
int a[N];
printf("Масив, заповнений випадковими числами:\n");
fillArrayRandom(a, N);
printArray(a, N);
quicksort(a, 0, N - 1);
printf("\nМасив, вiдсортований за допомогою швидкого сортування:\n");
printArray(a, N);
printf("\n\nВведiть %d чисел для сортування:\n", N);
for (int i = 0; i < N; i++) {
scanf("%d", &a[i]);
}
quicksort(a, 0, N - 1);
printf("\nВведений масив, відсортований за допомогою швидкого сортування:\n");
printArray(a, N);
return 0;
}
/*
* @file sort.h
* @author Герасимюк Д.В., гр. 515і1
* @date 07 квітня 2024
* @brief Лабораторна робота №4, варіант 3
* Функції. Швидке сортування. Робота з відлагоджувачем. Завдання 1
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#pragma once
void fillArrayRandom(int a[], int size) {
srand(time(NULL));
for (int i = 0; i < size; i++) {
a[i] = rand() % 151 - 50; //діапазон від -50..100
}
}
void printArray(int a[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", a[i]);
}
printf("\n");
}
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;
}
