Сортировка слиянием на языке C

Merge sort – один из самых эффективных алгоритмов сортировки, основанный на принципе "разделяй и сортируй". Он применяется для упорядочивания элементов в массиве. Merge sort рекурсивно разделяет массив на две равные части до тех пор, пока не останется массив из одного элемента. Затем производится слияние отсортированных подмассивов.

Процесс сортировки merge sort можно разделить на две основные стадии: разделение (или деление) и слияние.

1. Разделение:

   - Получаем индексы начала и конца массива.

   - Находим средний индекс.

   - Рекурсивно вызываем функцию сортировки merge sort для левой части массива (от начала до среднего индекса).

   - Рекурсивно вызываем функцию сортировки merge sort для правой части массива (от среднего индекса + 1 до конца массива).

2. Слияние:

   - Создаем временный массив для хранения отсортированных элементов.

   - Используем два указателя для обращения к элементам левой и правой частей массива.

   - Сравниваем элементы, указатели смещаются в соответствии с результатом сравнения:

   • Если элемент из левой части меньше или равен элементу из правой части, помещаем его во временный массив и смещаем левый указатель.
   • Если элемент из правой части меньше элемента из левой части, помещаем его во временный массив и смещаем правый указатель.

   - Повторяем предыдущие шаги, пока не закончатся элементы в одной из частей массива.

   - Копируем оставшиеся элементы из левой и правой части массива во временный массив.

   - Копируем элементы из временного массива обратно в исходный массив.

Пример кода на языке C:

include <stdio.h>

void merge(int arr[], int start, int mid, int end) {
    int leftSize = mid - start + 1;
    int rightSize = end - mid;

    int leftArr[leftSize], rightArr[rightSize];

    for (int i = 0; i < leftSize; i++) {
        leftArr[i] = arr[start + i];
    }
    for (int i = 0; i < rightSize; i++) {
        rightArr[i] = arr[mid + 1 + i];
    }

    int i = 0, j = 0, k = start;

    while (i < leftSize && j < rightSize) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    while (i < leftSize) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    while (j < rightSize) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int start, int end) {
    if (start < end) {
        int mid = start + (end - start) / 2;
        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {4, 2, 9, 6, 1, 8, 5, 3, 7};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("Исходный массив: ");
    printArray(arr, size);

    mergeSort(arr, 0, size - 1);

    printf("Отсортированный массив: ");
    printArray(arr, size);

    return 0;
}

Вывод программы:

Исходный массив: 4 2 9 6 1 8 5 3 7 
Отсортированный массив: 1 2 3 4 5 6 7 8 9 

Код представляет собой реализацию алгоритма merge sort на языке C. В функции merge происходит слияние отсортированных подмассивов, а функция mergeSort рекурсивно вызывает себя для разделения и сортировки массива. Функция printArray используется для вывода элементов массива. В главной функции main мы создаем исходный массив, вызываем mergeSort для его сортировки и выводим отсортированный массив.