Задачи модуля "Сортировки": от пузырьковой сортировки до слияния

Вспомните понятие "устойчивость" сортировки. Какая из этих двух сортировок не меняет относительный порядок равных элементов?

Сортировка вставкой.

Нам требуется устойчивая сортировка, которая не переставляет равные по ключу элементы относительно друг друга (в нашем случае ключ - это название города, например, Москва и Казань). Сортировка вставкой является устойчивой, поэтому внутри этих городов клиенты останутся отсортированными по сумме покупок. Сортировка выборкой - неустойчивая, и нарушила бы изначальный порядок внутри групп (городов).

Сначала максимум (корень) меняется местами с последним элементом кучи, а затем новый корень просеивается вниз (sift down), чтобы восстановить свойство Max-Кучи.

Ответ: [8, 4, 7, 3, 10] (при этом активная куча уменьшается на 1 элемент, а 10 остается на законном последнем месте).

• Шаг 1: Меняем корень 10 с последним элементом 3. Массив: [3, 8, 7, 4, 10]. (Куча теперь работает только с [3, 8, 7, 4]).
• Шаг 2 (SiftDown): Новый корень 3 нарушает свойства пирамиды. Его левый ребенок 8, правый 7. Максимум из детей - 8. Меняем 3 и 8 местами.
• Массив становится [8, 3, 7, 4, 10].
• Шаг 3: Элемент 3 (индекс 1) имеет ребенка 4 (индекс 3). 4 > 3, меняем их местами.
• Окончательный массив (для оставшейся кучи): [8, 4, 7, 3, 10].

Заведите логическую переменную (флаг), которую будете сбрасывать в начале каждого внешнего цикла и устанавливать при любом обмене элементов во внутреннем цикле.

Обычная пузырьковая сортировка всегда выполняет O(N²) операций. Оптимизация с флагом позволяет улучшить время работы до O(N) в лучшем случае (когда массив уже отсортирован или почти отсортирован).

Если во внутреннем цикле элементы ни разу не поменялись местами, это значит, что каждый элемент меньше или равен следующему, то есть массив отсортирован.

#include <stdio.h>
#include <stdbool.h>

void BubbleSortOptimized(int arr[], int n) {
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                // Обмен элементов
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swapped = true;
            }
        }
        // Если обменов не было - массив отсортирован
        if (!swapped) {
            break;
        }
    }
}

Функция partition должна перебрать все элементы подмассива и перенести те, что меньше опорного, в левую часть. Затем опорный элемент ставится между левой (меньшие) и правой (большие) частями.

Заведите указатель i (индекс меньшего элемента), который изначально равен low - 1. Пройдите циклом j от low до high - 1.

Внутри цикла, если arr[j] <= pivot, увеличивайте i и меняйте местами arr[i] и arr[j]. В конце не забудьте поменять arr[i+1] с arr[high] (опорным).

Сортировка Хоара работает по принципу "разделяй и властвуй".

1. Выбираем опорный элемент (pivot).
2. Перемещаем элементы так, чтобы слева от pivot оказались элементы меньше него, а справа - больше.
3. Рекурсивно сортируем левую и правую части.

Сложность: O(N log N) в среднем, но O(N²) в худшем случае (когда массив уже отсортирован, а мы берем последний элемент как pivot).

#include <stdio.h>

void Swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int Partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Выбираем последний элемент опорным
    int i = (low - 1);     // Индекс меньшего элемента

    for (int j = low; j <= high - 1; j++) {
        // Если текущий элемент меньше или равен pivot
        if (arr[j] <= pivot) {
            i++; 
            Swap(&arr[i], &arr[j]);
        }
    }
    // Ставим pivot на правильное место
    Swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void QuickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi - индекс опорного элемента после разделения
        int pi = Partition(arr, low, high);

        // Рекурсивно сортируем элементы до и после разделения
        QuickSort(arr, low, pi - 1);
        QuickSort(arr, pi + 1, high);
    }
}

Для слияния заведите два указателя: один на начало левой половины, второй на начало правой. На каждом шаге выбирайте меньший элемент и копируйте его во временный массив.

После прохода может оказаться так, что элементы в одной из половин закончились, а во второй еще остались. Их нужно просто скопировать в хвост результирующего массива.

В языке C вы можете использовать malloc для создания временных массивов размера n1 = m - l + 1 и n2 = r - m. Не забудьте освободить их память с помощью free().

Сортировка слиянием также использует "разделяй и властвуй", но в отличие от сортировки Хоара, деление всегда происходит ровно пополам.

Алгоритм стабильно работает за время O(N log N) как в лучшем, так и в худшем случае, что делает его предсказуемым. Однако, в отличие от алгоритмов, сортирующих "на месте", слияние требует дополнительной памяти O(N) для временного массива.

#include <stdio.h>
#include <stdlib.h>

void Merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    int* L = (int*)malloc(n1 * sizeof(int));
    int* R = (int*)malloc(n2 * sizeof(int));

    // Копируем данные во временные массивы
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

    // Сливаем временные массивы обратно в arr
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Копируем оставшиеся элементы L[]
    while (i < n1) {
        arr[k] = L[i];
        i++; k++;
    }

    // Копируем оставшиеся элементы R[]
    while (j < n2) {
        arr[k] = R[j];
        j++; k++;
    }
    
    free(L);
    free(R);
}

void MergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;

        MergeSort(arr, l, m);
        MergeSort(arr, m + 1, r);

        Merge(arr, l, m, r);
    }
}