Другая идея: менять соседей

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

Теперь попробуем совсем другой подход. Вместо того чтобы искать минимум и переносить его, будем сравнивать соседние элементы и менять их местами, если левый больше правого. Пойдём по массиву слева направо, шаг за шагом, и будем обменивать каждую «неправильную» пару. Посмотрим, что из этого получится.

Возьмём массив [5, 1, 4, 2, 8]. Сравниваем 5 и 1: 5 больше, меняем. Массив стал [1, 5, 4, 2, 8]. Сравниваем 5 и 4: 5 больше, меняем. Получаем [1, 4, 5, 2, 8]. Сравниваем 5 и 2: 5 больше, меняем. Получаем [1, 4, 2, 5, 8]. Сравниваем 5 и 8: не больше, не трогаем. Проход закончился. Результат: [1, 4, 2, 5, 8]. Пятёрка как будто «всплыла» к концу — прошла через несколько позиций, обмениваясь с каждым меньшим соседом.

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

Отсюда естественная структура алгоритма. Внешний проход повторяется, сокращая активную часть массива: сначала рассматриваем весь массив до n − 1, потом до n − 2, потом до n − 3, и так далее. С каждым проходом один элемент справа окончательно встаёт на своё место. Активная часть сокращается, потому что правый суффикс уже отсортирован.

Внутри каждого прохода идём по активной части слева направо и сравниваем соседние элементы: если a[j] больше a[j+1], меняем их местами. После полного прохода самый большой элемент активной части уходит в её конец.

Прогоним по нашему массиву. Первый проход по всему массиву [5, 1, 4, 2, 8] дал [1, 4, 2, 5, 8]. Восьмёрка на последней позиции, дальше её не трогаем. Второй проход по активной части [1, 4, 2, 5]: сравниваем 1 и 4 — не трогаем. Сравниваем 4 и 2 — меняем, получаем [1, 2, 4, 5]. Сравниваем 4 и 5 — не трогаем. Активная часть закончилась. Массив стал [1, 2, 4, 5, 8]. Заметим: пятёрка теперь стоит на предпоследней позиции, тоже окончательно.

Третий проход по активной части [1, 2, 4]. Сравниваем 1 и 2 — не трогаем. Сравниваем 2 и 4 — не трогаем. Ни одного обмена за весь проход. Вот тут и вступает в игру ранняя остановка.

Ранняя остановка и её обоснование

Зачем делать ещё проходы, если предыдущий не совершил ни одного обмена? Подумаем, что означает отсутствие обменов. Если за весь проход ни одна пара a[j], a[j+1] не оказалась «неправильной», значит, для всех j в активной части выполняется a[j] ≤ a[j+1]. Но это и есть определение упорядоченности по неубыванию! Значит, активная часть уже отсортирована, и продолжать нет смысла.

Важно понять, что проверка «не было обменов» работает именно за весь проход, а не за одну пару. Если мы посмотрели на пару и не поменяли её — это говорит только о ней, а не о соседних. Только полный проход без единого обмена доказывает, что все соседние пары в активной части удовлетворяют условию, а значит, и весь активный отрезок упорядочен.

Реализуется это так. Заводим переменную changed = false в начале каждого прохода. При каждом обмене устанавливаем changed = true. После завершения прохода проверяем: если changed осталось false — выходим из внешнего цикла, массив упорядочен.

Соберём программу. Функция сортирует массив на месте. Случай null отсекаем отдельно.

using System;

int[] prices = { 5, 1, 4, 2, 8 };
BubbleSort(prices);
Print(prices);

int[] empty = Array.Empty<int>();
BubbleSort(empty);
Print(empty);

int[] one = { 42 };
BubbleSort(one);
Print(one);

int[] negative = { -3, 5, -1, 0, -3 };
BubbleSort(negative);
Print(negative);

int[] equal = { 3, 3, 3 };
BubbleSort(equal);
Print(equal);

void BubbleSort(int[] a)
{
    if (a == null) throw new ArgumentNullException(nameof(a));
    int n = a.Length;
    for (int end = n - 1; end > 0; end--)
    {
        bool changed = false;
        for (int j = 0; j < end; j++)
        {
            if (a[j] > a[j + 1])
            {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                changed = true;
            }
        }
        if (!changed) break;
    }
}

void Print(int[] a)
{
    if (a.Length == 0)
    {
        Console.WriteLine("(пусто)");
        return;
    }
    Console.WriteLine(string.Join(" ", a));
}

Вывод:

1 2 4 5 8
(пусто)
42
-3 -3 -1 0 5
3 3 3

Разберём случаи. Основной массив [5, 1, 4, 2, 8] отсортирован в [1, 2, 4, 5, 8]. Пустой массив: внешний цикл начинается с end = −1, условие end > 0 ложно, ничего не выполняется, печатается «(пусто)». Один элемент: то же самое, остаётся 42. Отрицательные числа: сравнение работает с любыми int, [−3, 5, −1, 0, −3] превращается в [−3, −3, −1, 0, 5]. Массив из трёх равных троек уже упорядочен, первый проход не совершит ни одного обмена, сработает ранняя остановка.

Разберём два случая. Худший — когда массив упорядочен в обратном порядке или близок к этому. На первом проходе делается n − 1 сравнений, на втором n − 2, и так далее, до одного. Это то же самое, что у сортировки выбором: n(n − 1)/2 сравнений, O(n²) по времени. Обменов в худшем случае тоже порядка n² — на каждом сравнении происходит обмен. Это заметно больше, чем у выбора, где обменов не больше n − 1.

Лучший случай — когда массив уже отсортирован. Первый проход делает n − 1 сравнение и не совершает ни одного обмена. Ранняя остановка срабатывает, внешний цикл завершается. Итого n − 1 сравнение, то есть O(n) по времени. Обменов ноль. Вот здесь пузырьковая сортировка выигрывает у выбора: она реагирует на упорядоченность, а выбор — нет.

Вспомогательная память — O(1): только счётчики и временная переменная для обмена. Массив сортируется на месте.

Стабильность и тонкость со знаком сравнения

Условие обмена — строгое a[j] > a[j+1]. Это не случайность, а важная деталь. Если соседние элементы равны, условие ложно, обмена не происходит. Значит, равные элементы никогда не меняются местами друг с другом. Если в массиве были объекты с одинаковыми ключами, их относительный порядок сохраняется. Сортировка пузырьком — стабильна.

А теперь представим, что мы случайно написали >= вместо >. Тогда равные соседи тоже будут обмениваться: a[j] = a[j+1] и a[j+1] = a[j] — формально то же самое, но если за значениями стоят объекты с дополнительными данными, обмен меняет их взаимный порядок. Стабильность теряется. Ещё один повод внимательно относиться к знаку сравнения: иногда он влияет не на результат сортировки, а на её свойство сохранять порядок равных.

Здесь легко сделать поспешный вывод. Раз пузырьковая сортировка умеет останавливаться рано, значит, на почти отсортированных данных она работает быстро. Это не всегда так. Возьмём массив [2, 3, 4, 5, 1]. Он почти отсортирован: только единица стоит не на месте. Но посмотрим, что делает пузырьковая сортировка. Первый проход: 2 и 3 — не трогаем, 3 и 4 — не трогаем, 4 и 5 — не трогаем, 5 и 1 — меняем. Получаем [2, 3, 4, 1, 5]. Единица сдвинулась влево только на одну позицию. Второй проход: 4 и 1 меняем, единица сдвигается ещё на одну позицию. [2, 3, 1, 4, 5]. И так далее. Чтобы единица добралась до начала, нужно n − 1 проходов, и на каждом — свои обмены.

Причина в том, что пузырьковая сортировка двигает маленький элемент влево лишь на одну позицию за проход. Большие элементы улетают вправо быстро, а маленькие ползут влево медленно. В этом примере выполнятся все n − 1 проходов: каждый содержит обмен, поэтому раньше завершиться не получится. Значит, на таком семействе входов, где один маленький элемент застрял в конце, пузырьковая сортировка остаётся квадратичной. Ранняя остановка помогает на действительно упорядоченных данных, но не на всяком «почти».

Полезно сопоставить два разобранных алгоритма. Сортировка выбором делает мало обменов — не больше n − 1 — но всегда одинаковое число сравнений, независимо от исходного порядка. Она не адаптируется. Пузырьковая сортировка делает больше обменов в худшем случае, но зато умеет замечать упорядоченность и останавливаться рано. Кроме того, пузырьковая сортировка стабильна, а выбором — нет.

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