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

Lesson_03/Task_1/Task_1.cpp
104 строки3 KB
AirLexa
создал Lesson_03/Task_1/Task_1.cpp
28 дек 2025, 15:44
28 дек 2025, 15:44b148627
#include <iostream>
#include <windows.h>

void merge(int* arr, int l, int m, int r) {

    int size_1 = m - l + 1; // размер левого подмассива
    int size_2 = r - m;    // размер правого подмассива

    // создаем временные подмассивы 
    int* tmp_1 = new int[size_1]; // это слева
    int* tmp_2 = new int[size_2]; // это справа

    // копируем ячейки во временные подмассивы
    for (int i = 0; i < size_1; i++)
        tmp_1[i] = arr[l + i];
    for (int i = 0; i < size_2; i++)
        tmp_2[i] = arr[m + 1 + i];

    int le = 0; // индекс левого массива
    int ri = 0; // индекс правого массива
    int gn = l; // индекс основного массива куда будем вносить элементы

    while (le < size_1 && ri < size_2) { // пока не будет достигнут конец подмассива
        if (tmp_1[le] <= tmp_2[ri]) { // если левый элемент меньше правого, 
            arr[gn] = tmp_1[le]; // то его и записываем
            le++; // и смещаемся на следующий
        }
        else {
            arr[gn] = tmp_2[ri];// иначе записываем туда правый элемент
            ri++; // и тоже смещаемся
        }
        gn++; // основной массив, тоже смещаемся вправо
    }

    // если правый массив закончился быстрее, 
    // то оставшиеся левые переписываем в основной
    while (le < size_1) {
        arr[gn] = tmp_1[le];
        le++;
        gn++;
    }

    // тоже самое с правым массивом
    while (ri < size_2) {
        arr[gn] = tmp_2[ri];
        ri++;
        gn++;
    }

    // удаляем временные массивы
    delete[] tmp_1;
    delete[] tmp_2;
}

void sort(int* arr, int l, int r) {
    if (l == r) return; // нет середины, выходим
    // ищем середину
    int m = (l + r) / 2;

    // левая и правая половины массива
    sort(arr, l, m);
    sort(arr, m + 1, r);

    // объединяем отсортированные половины
    merge(arr, l, m, r);
}

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 merge_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 };
    merge_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 };
    merge_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 };
    merge_sort(arr, size);
    delete[] arr;

    return 0;
}