/**
* @file FP.cpp
* @autor Батуріна В. 515б
* @date 15.05.2023
* @brief Лабораторна робота №4, варіант 19
*
* Функції. Швидке сортування. Робота з відлагоджувачем. Завдання 1
*/
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
#include <time.h>
#include "head.h"
int main() {
setlocale(LC_ALL, "Ukr");
srand(time(NULL));
//переменные
int size = 0;
int cor = 0;
char fill = ' ';
int arr[MAX_SIZE] = { 0 };
//размер массива
while (size < 2 || size > 100) {
if (cor >= 1)
printf("Ошибка.");
printf("Введите размер массива от 2 до 100: \n");
cor++;
scanf("%i", &size);
}
cor = 0;
//тип заполнения
while (fill != 'f' && fill != 'r') {
if(cor >= 1)
printf("Ошибка.");
printf("Введите метод заполнения массива:\n"
"\tf - заполнение пользователем\n"
"\tr - заполнение случайными числами\n"
);
cor++;
if (getchar() == '\n')
fill = getchar();
fill = getchar();
}
//заповнення масиву
switch (fill) {
case 'f':
for (size_t i = 0; i < size; i++) {
scanf("%i", &arr[i]);
}
break;
default:
for (size_t i = 0; i < size; i++) {
arr[i] = rand() % 10;
}
break;
}
printf("Ваш маcсив:");
for (size_t i = 0; i < size; i++) {
printf(" %i", arr[i]);
}
printf("\n\n");
quicksort(arr, size, 0, size - 1);
printf("Ваш отсортированный массив:");
for (size_t i = 0; i < size; i++) {
printf(" %i", arr[i]);
}
printf("\n\n");
//завершення програми
printf("Конец.");
return 0;
}
#define MAX_SIZE 100
/** * Швидке сортування
*
* @param Array – масив збереження чисел, в якому відбудеться сортування
* @param N – розмір масиву
* @param L – лівий флаг
* @param R – правий флаг
* @return void
*/
void quicksort(int Array[], unsigned int N, int L, int R);
#include <stdio.h>
#include "head.h"
//функция быстрой сортировки
void quicksort(int Array[], unsigned int N, int L, int R) {
//создание переменных
int iter = L, jter = R;
//срездние число
int middle = (R + L) / 2;
//средний елемент
int x = Array[middle];
int w;
//цыкл сортировки
do {
//поиск в левой границе, чсла больше чем х
while (Array[iter] < x) {
iter++;
}
//поиск в правой границе, чсла больше чем х
while (x < Array[jter]) {
jter--;
}
//сортировка
if (iter <= jter) {
w = Array[iter];
Array[iter] = Array[jter];
Array[jter] = w;
iter++;
jter--;
}
} while (iter < jter);
//рекурсия по левому елементу
if (L < jter) {
quicksort(Array, N, L, jter);
}
//рекурсия по правому елементу
if (iter < R) {
quicksort(Array, N, iter, R);
}
}
