Сортировка Шелла: вставки с прыжками

Если ты понимаешь, что сортировка Шелла - это вставки по убывающим шагам, почему прыжки бьют квадрат и почему последний шаг всегда 1, листай до «Теперь сам».

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

У вставок одна беда: элемент двигается к своему месту по ОДНОЙ позиции за раз. Если маленькое число застряло в самом конце, вставкам придётся протащить его через весь массив - n сдвигов на один элемент. Отсюда и Θ(n²) в худшем случае. Напрашивается вопрос: а нельзя ли двигать элементы БОЛЬШИМИ прыжками, чтобы далеко стоящее число быстро оказывалось рядом с местом? Дональд Шелл в 1959-м ответил «можно» - и получил сортировку, которая простой правкой вставок пробивает квадратичный потолок.

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

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

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

Выбираем последовательность убывающих шагов, оканчивающуюся на 1, например 4, 2, 1. Для каждого шага gap делаем сортировку ВСТАВКАМИ, но «соседом» считаем элемент на gap позиций левее, а не на одну. То есть массив как бы разбит на gap независимых подпоследовательностей (элементы через gap), и каждая сортируется вставками. При gap = 4 элемент за один сдвиг перепрыгивает сразу через четыре позиции. Уменьшаем gap и повторяем. Последний проход gap = 1 - это обычные вставки, но массив к нему подходит уже почти упорядоченным, поэтому линеен.

Правило

Сортировка Шелла - это сортировка вставками по убывающим шагам gap, оканчивающимся на 1. Большие шаги дальними прыжками наводят грубый порядок, снимая главную слабость вставок (движение по одной позиции); последний проход gap = 1 доводит уже почти упорядоченный массив за линию. Итог - быстрее Θ(n²): при хороших шагах около Θ(n^1.5). Точная оценка зависит от выбора последовательности шагов - это до сих пор не до конца решённый вопрос.

Разбор: почему прыжки бьют квадрат

Слабость вставок - в том, что беспорядок они устраняют по чуть-чуть: один сдвиг убирает ровно одну инверсию (пару не по порядку). Если инверсий Θ(n²), столько и работы. Шаг gap > 1 устраняет инверсию МЕЖДУ ДАЛЁКИМИ элементами за один обмен - то есть убирает сразу много «мелких» будущих инверсий. Когда после крупных шагов доходит до gap = 1, инверсий осталось мало (близких пар не по порядку), и финальные вставки почти линейны. Грубо: крупные шаги дёшевы (подпоследовательности короткие), а мелкие работают на уже упорядоченном - и суммарно выходит меньше квадрата. Именно поэтому важно, чтобы шаги шли по УБЫВАНИЮ и последний был 1: без gap = 1 массив не будет отсортирован до конца (внутри соседних пар порядок не гарантирован), а без предварительных крупных шагов это просто медленные вставки.

Разбор: почему последний шаг обязан быть 1

Пока gap > 1, сортировка упорядочивает только элементы, отстоящие на кратное gap, - внутри каждой подпоследовательности. Соседние элементы (на расстоянии 1), попавшие в разные подпоследовательности, между собой не сравнивались ни разу. Значит массив ещё не обязан быть отсортирован. Гарантию даёт только проход gap = 1: он сравнивает всех соседей и добивает остаток порядка. Крупные шаги - это подготовка, а корректность обеспечивает единичный шаг. Поэтому любая последовательность шагов Шелла ОБЯЗАНА заканчиваться на 1 - иначе сортировка неверна.

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

Первая ошибка - забыть завершить последовательность шагов единицей: сортировка отработает и вернёт МАССИВ, который не отсортирован (соседи из разных подпоследовательностей так и не сравнились). Верный на вид код молча даёт неверный порядок. Вторая - взять плохую последовательность шагов (например, только степени двойки ..., 8, 4, 2, 1): чётные шаги долго не дают нечётным и чётным позициям «встретиться», и оценка деградирует ближе к Θ(n²). Выбор шагов - не мелочь: от него зависит вся скорость. Третья - ждать от Шелла устойчивости: дальние прыжки переставляют равные элементы, устойчивость теряется.

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

Сортировка Шелла - показательный урок «маленькая правка идеи меняет асимптотику»: из квадратичных вставок она делает субквадратичную сортировку, не усложняя код почти ничем и не требуя дополнительной памяти. На практике её берут там, где нужна приличная скорость при минимуме кода и без выделения памяти (встроенные системы, ядра, места с жёсткими ограничениями по памяти, где рекурсия быстрой сортировки нежелательна). Для общего случая её вытеснили n·log n-сортировки, но как идея «улучшить простой алгоритм крупными шагами» она встречается снова и снова - и показывает, что даже у школьного алгоритма есть куда расти.

Теперь сам

Массив [5, 2, 8, 1] сортируют Шеллом с шагами 2, 1. Что произойдёт на шаге gap = 2 и почему после него нельзя останавливаться?