Простые сортировки

В каталоге USGS 462 землетрясения силой от 6,5 за 2015–2025 годы. Каталог хранит их по времени, а нам нужна таблица по силе, от слабых к сильным. Вручную такой список упорядочивают тремя способами, и все три знакомы с детства: найти самое слабое и положить первым; брать карточки по одной и вставлять каждую на своё место; менять местами соседей, пока все не встанут как надо. Ниже — все три на настоящем каталоге, бок о бок. Полоска — землетрясение, высота — сила, цвет — дата. Переключите набор и порядок на входе: «таблица + 2025» — это отсортированная таблица прошлых лет, в конец которой дописали события нового года.

Выбор на 462 землетрясениях делает 106 491 сравнение при любом порядке входа — ровно столько, сколько пар можно составить из 462 элементов. Вставкам на исходный порядок нужно 47 801 сравнение, а на «таблицу + 2025» — всего 8985: каждое новое землетрясение проезжает влево только до своего места. Пузырёк на той же таблице не сэкономил ни одного сравнения: 103 488, столько же, сколько на исходном порядке. Почему так выходит, видно из того, как они устроены. А когда все трое закончат, присмотритесь к цвету внутри каждой ступеньки одинаковой силы.

Идея

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

Что именно растёт, у каждого своё, и от этого зависит всё остальное:

Как работает каждый

Выбор. Просматриваем все оставшиеся элементы, запоминаем наименьший и меняем его местами с первым из оставшихся. Чтобы убедиться, что элемент наименьший, нужно сравнить его со всеми остальными, и никакая удача входа от этой работы не избавляет: на уже отсортированном массиве выбор тратит те же n(n − 1)/2 сравнений. Зато обмен на проход — один, а если наименьший уже стоит на месте, то ни одного.

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

Пузырёк. Идём слева направо и меняем местами соседей, если левый больше. Наибольший элемент, раз попавшись, едет вправо до самого конца — за один проход. Если за проход не случилось ни одного обмена, массив отсортирован и можно остановиться. У пузырька заметная асимметрия: большой элемент в начале добирается до конца за один проход, а маленький в конце сдвигается влево лишь на одну позицию за проход. В «таблице + 2025» новые землетрясения стоят в самом конце, самым слабым из них ехать почти через весь массив, и пузырьку нужно почти столько же проходов, сколько элементов. Вставки берут такой элемент и проводят до места за один раз. Пузырёк можно подлечить, чередуя направление проходов (так называемая шейкерная сортировка), но квадрат никуда не денется.

Почему квадрат: инверсии

Мерило беспорядка в массиве — инверсии: пары, в которых больший элемент стоит левее меньшего. В отсортированном массиве их нет, в развёрнутом — все n(n − 1)/2 пар. У 462 землетрясений в порядке времени инверсий 47 340, у «таблицы + 2025» — 8524.

Сколько инверсий в случайном массиве? Возьмём различные элементы в случайном порядке. Если развернуть массив задом наперёд, каждая пара, бывшая инверсией, перестанет ею быть, и наоборот. Перестановка и её разворот равновероятны, поэтому каждая из n(n − 1)/2 пар оказывается инверсией с вероятностью ровно 1/2, и в среднем инверсий n(n − 1)/4. Отсюда приговор всем алгоритмам, которые двигают элементы на одну позицию за раз: на случайных данных им нужно порядка n² перестановок, как ни старайся.

Посмотрите на это вживую. Ниже 45 землетрясений силой от 6,5 за 2025 год; каждая клетка треугольника — пара, которая стоит не в том порядке. Синие клетки исчезают по одной на каждый обмен вставок и пузырька — и ни одной больше.

Переключите на выбор. Его длинный обмен разворачивает сразу много пар: элемент перелетает через весь массив и меняет порядок со всеми, кого миновал. Иногда при этом появляются и новые инверсии, а оранжевые клетки — это пары равной силы, которые выбор переставил по пути. Чтобы быстро сортировать, нужно двигать элементы далеко — это и делают сортировка слиянием, быстрая и пирамидальная. Самый короткий мостик от вставок к ним придумал Дональд Шелл в 1959 году: сначала делать вставки с большим шагом, через h позиций, и уменьшать шаг до единицы.

Из теоремы следует и сила вставок. Каждое сравнение у них либо сдвигает элемент, убирая одну инверсию, либо останавливает его, а остановок не больше n − 1. Поэтому сравнений не больше I + n − 1, и время — O(n + I). Сортировку, которая работает тем быстрее, чем ближе вход к отсортированному, называют адаптивной. На «таблице + 2025» инверсий 8524 — и сравнений 8985.

Устойчивость: что бывает с равными

Магнитуды в каталоге записаны в основном с одним знаком после запятой, и у 462 землетрясений всего 20 разных значений: почти у каждого есть ровесники по силе. Сортировка по силе ничего не говорит о том, в каком порядке должны идти равные, — и алгоритмы ведут себя по-разному. Сортировку называют устойчивой, если равные элементы выходят из неё в том же порядке, в каком вошли.

Вставки и пузырёк устойчивы. Вставки останавливают новый элемент перед первым, кто не больше его, и равный элемент никогда не обгоняет равного; пузырёк меняет соседей, только если левый строго больше. В первой сцене это видно по цвету: внутри каждой ступеньки одинаковой силы цвет идёт от тёмного к светлому, от 2015 года к 2025-му. У выбора цвета перемешаны: его дальний обмен уносит элемент через головы равных ему. На 462 землетрясениях выбор переставил 2284 пары равной силы. Вот то же на двадцати землетрясениях 2025 года силой от 6,9 — даты внутри групп равной силы после сортировки выбором:

selection: 190 comparisons, 18 swaps
  6.9: 04-03 04-04 07-30 09-30
  7.0: 07-28 03-30 12-06  <- out of date order
  7.4: 07-20 09-13 10-10 05-02  <- out of date order
  7.6: 02-08 10-10 12-08

Зачем это нужно: сортировка по нескольким ключам. Отсортируйте таблицу по дате, потом устойчиво — по силе, и внутри одной силы записи останутся по дате, без составного ключа. Встроенная сортировка Python устойчива всегда. В Go обычные sort.Sort и slices.Sort устойчивость не обещают, а sort.Stable и slices.SortStableFunc — обещают. Устойчивость легко потерять по невнимательности: замените во вставках «строго меньше» на «не больше», и массив по-прежнему отсортируется, но равные станут обгонять друг друга, а сдвигов прибавится.

Код

Все три функции сортируют на месте и возвращают счётчики: сравнения и перестановки. В Python сравнение идёт по ключу, как у встроенной sorted; в Go — через функцию «меньше» и обобщённый тип, как в пакете slices. Демо — двадцать землетрясений 2025 года силой от 6,9.

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

А это первая сцена в виде программы: все 462 землетрясения силой от 6,5 из каталога на сервере, три порядка на входе, три алгоритма. Цифры совпадают с теми, что показывала сцена.

Сколько это стоит

Памяти все трое берут O(1): пара индексов и один элемент «в руке». Время считаем в сравнениях и перестановках, для n различных элементов:

Лучший случай вставок и пузырька — уже отсортированный массив, худший — развёрнутый. Ниже замер на случайных числах, на Python и на Go. Оси логарифмические, и наклон прямой — показатель степени: у трёх квадратичных он близок к 2, у вставок на почти готовой таблице (отсортированные числа и десять новых в конце) — к 1. Для сравнения — встроенная сортировка на случайных данных.

Пузырёк медленнее всех и на Python, и на Go: сравнений у него вдвое больше, чем у вставок, а каждый обмен — две записи в память. Вставки на Go почти втрое быстрее выбора, ведь сравнений у них в среднем вдвое меньше. На Python же они почти сравнялись: интерпретатор тратит на каждый шаг цикла while со сдвигом больше, чем на шаг цикла for у выбора, и выигрыш в числе сравнений съедается. Это хороший повод мерить, а не считать на бумаге. И ещё одно: на Python встроенная сортировка шестидесяти четырёх тысяч чисел заканчивается раньше, чем любая из квадратичных справляется с полутора тысячами.

Где они работают

Вставки — внутри быстрых сортировок. Сортировка слиянием и быстрая сортировка хороши на больших массивах, но на кусках из десятка элементов их накладные расходы — вызовы, разбиения, буферы — больше самой работы. Поэтому многие стандартные библиотеки добивают маленькие куски вставками. Timsort в Python сортирует список короче 64 элементов целиком двоичными вставками (место ищут двоичным поиском), а короткие упорядоченные куски длинных списков вставками же доращивает до 32–64 элементов. Сортировка в Go переходит на вставки на кусках до 12 элементов, std::sort в libstdc++ — до 16, Arrays.sort для массивов чисел в Java — до 44. У вставок нет рекурсии, они читают память подряд и почти ничего не делают на почти готовых данных.

Вставки — когда данные приходят по одному. «Таблица + 2025» — ровно этот случай: отсортированный список и несколько новых записей. Вставка одной записи — один проход влево. Для больших таблиц, куда записи идут потоком, лучше дерево поиска или куча, но для сотни-другой строк вставки проще и быстрее всего.

Выбор — когда перестановка дорога. Выбор делает не больше n − 1 обменов, а на различных элементах — ровно столько, сколько необходимо: каждый его обмен ставит на окончательное место хотя бы один элемент (почему ровно столько и не меньше — в задаче о коробках в архиве). Это важно, когда переставлять гораздо дороже, чем сравнивать, — тяжёлые записи, медленная запись в память. А если искать минимум не просмотром, а кучей, выбор превращается в пирамидальную сортировку за O(n log n).

Пузырёк в настоящем коде почти не встречается: он делает столько же перестановок, сколько вставки, но больше сравнений и вдвое больше записей. Дональд Кнут в третьем томе «Искусства программирования» заметил, что достоинств у него, кажется, нет, кроме запоминающегося названия и пары интересных теоретических задач. Его место — в учебниках, как самая короткая программа, которая сортирует.

Откуда имена

В 1956 году Эдвард Френд в журнале JACM разобрал сортировку на электронных машинах и сравнил вставки, выбор и обмены. Об обменах он писал, что им нужно по меньшей мере вдвое больше сравнений, чем вставкам, и на большинстве машин они будут хуже. Слова «пузырёк» там ещё нет: его, по поискам Оуэна Астракана (2003), первым напечатал Кеннет Айверсон в книге «A Programming Language» 1962 года. До того алгоритм звали «сортировкой обменами». В 1963 году он попал в сборник алгоритмов ACM как Algorithm 175 под именем Shuttle Sort — и вскоре в опубликованном коде нашли ошибки.

А в 1959 году Тони Хоар, тогда университетский стажёр, работал над машинным переводом. Русско-английский словарь хранился на магнитной ленте по алфавиту, и слова предложения выгодно было сначала отсортировать, чтобы найти их все за один проход ленты. По воспоминаниям Хоара, первым ему пришёл в голову тот способ, который теперь называют пузырьком, — и он отверг его как слишком медленный. Вторым была быстрая сортировка.

Задачи

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