Пузырьковые сортировки (Bubble Sort)

Также упоминается как: метод пузырька, сортировка простым обменом (академическое название), сортировка обменами (exchange sort)

Самый знаменитый учебный алгоритм. Основан на локальных обменах соседних элементов, которые постепенно приводят к глобальной упорядоченности.

Алгоритм работы

• Последовательно проходим по массиву слева направо. Сравниваем два соседних элемента: если левый больше правого, меняем их местами.
• После первого полного прохода самый большой ("тяжелый") элемент неизбежно окажется в самом конце массива, подобно пузырьку воздуха.
• На втором проходе на предпоследнее место всплывет второй по величине элемент, и так далее.
• Оптимизация: если за полный проход не было ни одного обмена, массив уже отсортирован - работу можно прервать!

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

Данный метод устойчив (если строго >, а не >=), но из-за огромного количества обменов на каждом шаге он крайне медленный на практике.

Другие пузырьковые сортировки

Обмен соседних элементов породил не один алгоритм, а целое семейство. Все они делают одно и то же и различаются лишь тем, в каком порядке перебирают пары - поэтому о пузырьковых сортировках говорят во множественном числе.

• Шейкерная сортировка (Cocktail Shaker Sort), она же сортировка перемешиванием и двунаправленная пузырьковая. Проходы идут попеременно слева направо и справа налево. Это лечит главную беду оригинального алгоритма: маленький элемент в конце массива добирается до начала за один проход, а не за N.
• Сортировка расческой (Comb Sort). Сравниваются не соседи, а элементы на расстоянии, которое сокращается от прохода к проходу. Идея та же, что у сортировки Шелла, и на практике расческа ведет себя заметно лучше квадратичной.
• Гномья сортировка (Gnome Sort), она же глупая сортировка. После обмена алгоритм возвращается на шаг назад вместо того, чтобы идти дальше. Пишется одним циклом без вложенного и потому часто служит самым коротким примером сортировки вообще.
• Чет-нечетная сортировка (Odd-Even Sort), она же кирпичная (brick sort). Проход разбит надвое: сначала пары с четными индексами, затем с нечетными. Внутри половины обмены не мешают друг другу, поэтому такую сортировку легко распараллелить.

Пузырьковая сортировка: реализация на C с оптимизацией

#include <stdbool.h>

void BubbleSort(int arr[], int n) {
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false; // Флаг: были ли обмены в этом проходе?
        
        // Внутренний цикл до n-i-1, так как 'i' элементов уже всплыли в конец
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                Swap(&arr[j], &arr[j + 1]);
                swapped = true;
            }
        }
        // Если обменов не было, массив отсортирован - выходим досрочно!
        if (!swapped) break;
    }
}