/**
* @file main.c
* @author Мосяж А.М., гр. 515б
* @date 01 травня 2023
* @brief Лабораторна робота № 4, варіант 4
* Швидке сортування Завдання 1
*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <locale.h>
#include "qfun.h"
int main()
{
setlocale (LC_ALL, "Ukr");
int* arr;
int n, md;
printf("\nГенерувати випадково(1) чи ввести елементи вручну(2): ");
scanf("%d", &md);
printf("\nРозмір масиву: ");
scanf("%d", &n);
arr = (int*)malloc(sizeof(int) * n);
if (md == 2)
manualInit(arr, n);
else
randomInit(arr, n);
printf("Оригінальний масив: ");
printarr(arr, n);
quicksort(arr, 0, n - 1);
printf("Сортований масив: ");
printarr(arr, n);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
int split(int* a, int low, int high, int part_element)
{
int i = low - 1;
int j = high + 1;
while (1)
{
do
{
i++;
} while (a[i] > part_element);
do
{
j--;
} while (a[j] < part_element);
if (i >= j)
{
return j;
}
swap(&a[i], &a[j]);
}
}
void quicksort(int* arr, int low, int high)
{
if (low < high)
{
int part_element = arr[(low + high) / 2];
int i = split(arr, low, high, part_element);
quicksort(arr, low, i);
quicksort(arr, i + 1, high);
}
}
void manualInit(int* a, int n)
{
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
}
void randomInit(int* a, int n)
{
for (int i = 0; i < n; i++)
a[i] = rand() % 99;
}
void printarr(int* a, int n)
{
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n");
}
void swap(int* a, int* b);
int split(int* a, int low, int high, int part_element);
void quicksort(int* arr, int low, int high);
void manualInit(int* a, int n);
void randomInit(int* a, int n);
void printarr(int* a, int n);
