Lesson_03/Task_2/Task_2.cpp - master - AirLexa/03

Lesson_03/Task_2/Task_2.cpp
65 строк2 KB
AirLexa
создал Lesson_03/Task_2/Task_2.cpp
28 дек 2025, 15:46
28 дек 2025, 15:462009377
#include <iostream>
#include <windows.h>

void swap(int* arr, int a, int b)
{
    int tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}

void sort(int* arr, int beg, int end)
{
    // проверка на корректновсть, опорный элемент крайний
    if (beg >= end) return;
    
    // проверяем все элементы относительно элемента с индексом beg
    int cur = beg;
    for (int i = beg + 1; i <= end; i++) // если элемент меньше начального,     
        if (arr[i] < arr[beg]) swap(arr, ++cur, i); // меняем его с левым 
    swap(arr, beg, cur); // меняем начальный и последний обмененный элементы
    
    // cортируем элементы слева
    if (cur > beg) sort(arr, beg, cur - 1); 

    // cортируем элементы справа
    if (end > cur + 1) sort(arr, cur + 1, end);
}

void print_arr(std::string str, int* arr, int size)
{
    std::cout << str;
    for (int i = 0; i < size; i++)
        std::cout << " " << arr[i];
    std::cout << std::endl;
}

void quick_sort(int* arr, int size)
{
    print_arr("Исходный массив:", arr, size);
    sort(arr, 0, size - 1);
    print_arr("Отсортированный массив:", arr, size);
}

int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);

    int size = 10;
    int* arr = new int[size] { 3, 43, 38, 29, 18, 72, 57, 61, 2, 33 };
    quick_sort(arr, size);
    delete[] arr;

    size = 15;
    arr = new int[size] { 88, 91, 87, 59, 53, 49, 29, 16, 4, 27, 28, 89, 2, 25, 74 };
    quick_sort(arr, size);
    delete[] arr;

    size = 18;
    arr = new int[size] { 24, 66, 20, 79, 30, 16, 19, 62, 94, 59, 0, 7, 59, 90, 84, 60, 95, 62 };
    quick_sort(arr, size);
    delete[] arr;

    return 0;
}