Сортировка выбором и пузырьком: два простых квадрата

Если ты знаешь, как работают сортировки выбором и пузырьком, почему обе Θ(n²) и чем они различаются по числу обменов, листай до «Теперь сам».

Как думаешь, как отсортировать массив «в лоб»

Самый прямой способ, который приходит в голову: найди самый маленький элемент и поставь его первым; из оставшихся снова найди самый маленький и поставь вторым; и так до конца. Это работает и называется сортировкой выбором. Другой прямой способ: проходи по массиву и, встретив пару соседей не по порядку, меняй их местами; повторяй, пока меняться перестанет. Это пузырёк. Оба честно сортируют - и оба, как мы сейчас посчитаем, стоят Θ(n²). С них и начнём, чтобы дальше было с чем сравнивать быстрые.

На что это похоже

Сортировка выбором - это как раскладывать карты, каждый раз выбирая из руки самую младшую и кладя её в стопку слева. Ты всякий раз просматриваешь ВСЮ оставшуюся руку, чтобы найти младшую, - потому и много сравнений. Пузырёк - как пузырьки воздуха в воде: лёгкий (большой элемент) всплывает наверх, обмениваясь местами с каждым соседом по пути. За один проход самый большой обязательно доходит до конца, следующий по величине - почти до конца, и так далее.

Механизм: два прохода по убывающему остатку

Выбором. Массив мысленно делится на разложенную часть слева и неразложенную справа. На каждом шаге ищем минимум неразложенной части (проход по ней) и меняем его с первым неразложенным элементом - граница разложенного сдвигается на один вправо. Внешних шагов n, внутренний проход на k-м шаге просматривает n − k элементов: (n−1) + (n−2) + ... + 1 = n(n−1)/2 = Θ(n²) сравнений. А вот обменов ровно n − 1 - по одному на внешний шаг: Θ(n).

Пузырьком. Проходим массив слева направо, сравнивая соседей a[i] и a[i+1]; если они не по порядку - меняем. За один проход самый большой элемент «всплывает» в конец. Повторяем проходы (каждый следующий на один короче - хвост уже разложен). Тех же Θ(n²) сравнений, но обменов - до Θ(n²): каждый неверный сосед требует обмена.

Правило

Сортировка выбором ищет минимум остатка и ставит на место: Θ(n²) сравнений всегда, но лишь Θ(n) обменов. Сортировка пузырьком меняет местами соседей не по порядку, всплывая большие элементы в конец: Θ(n²) сравнений и до Θ(n²) обменов. Обе квадратичны и годятся только для очень маленьких массивов; у пузырька можно рано выйти, если за проход не было ни одного обмена.

Разбор: почему сравнений именно n(n−1)/2

Возьмём выбором на n = 4. Первый внешний шаг ищет минимум среди четырёх - 3 сравнения (первый берём за кандидата, сравниваем с тремя). Второй шаг - среди трёх оставшихся, 2 сравнения. Третий - среди двух, 1 сравнение. Четвёртый остаётся сам собой. Итого 3 + 2 + 1 = 6 = 4·3/2. В общем виде (n−1) + (n−2) + ... + 1 = n(n−1)/2 - тот самый арифметический ряд из раздела про суммы, он растёт как n²/2, то есть Θ(n²). Число сравнений НЕ зависит от того, был ли массив уже отсортирован: выбором честно просматривает весь остаток каждый раз. Поэтому у неё нет «лучшего случая» - всегда Θ(n²).

Разбор: выбором и пузырёк - в чём разница на практике

Сравнений у обеих поровну (Θ(n²)), а вот обменов - нет, и это важно. Выбором делает ровно n − 1 обменов: нашла минимум - один раз переставила. Пузырёк делает обмен на КАЖДОЙ неверной паре соседей, а их может быть до Θ(n²). Обмен дороже сравнения (три присваивания против одного), поэтому там, где запись в память дорога (а перестановка - это запись), выбором выгоднее пузырька: меньше всего трогает данные. Отсюда правило выбора между двумя «плохими»: если элементы большие и копировать их дорого, из этих двух бери выбором - она минимизирует число перемещений.

Что ломается без этого

Главная ошибка - применить квадратичную сортировку к большим данным. На миллионе элементов Θ(n²) - это 10¹² операций, часы работы там, где n·log n-сортировка справится за секунду. Квадратичные сортировки живут только на очень коротких массивах (десятки элементов) или как учебный ориентир. Вторая ошибка - считать, что у любой сортировки есть «быстрый случай» на почти упорядоченных данных: у сортировки выбором его НЕТ, она всегда Θ(n²), потому что каждый раз просматривает весь остаток. А вот у пузырька и у сортировки вставками (следующий урок) такой случай есть.

Зачем это в работе

Эти сортировки почти никогда не пишут руками - в любом языке есть встроенная быстрая. Но знать их надо по трём причинам. Первая: они - база сравнения, точка отсчёта «как плохо бывает» и почему n·log n - это выигрыш. Вторая: на очень маленьких массивах (скажем, до 10-20 элементов) быстрые сортировки внутри себя ПЕРЕКЛЮЧАЮТСЯ на простую (обычно вставками), потому что у неё меньше накладных расходов - об этом в последней главе раздела. Третья: разница «выбором дёшева по обменам» - это первый пример того, что у сортировки несколько метрик стоимости (сравнения и перемещения), и выбор зависит от того, что дорого именно у тебя.

Теперь сам

Массив [3, 1, 2] сортируют выбором. Опиши по шагам, что происходит, сколько будет сравнений и сколько обменов. Почему число сравнений не изменится, даже если подать уже отсортированный [1, 2, 3]?