Сортировка вставками: адаптивная и устойчивая

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

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

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

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

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

Механизм: вставить в отсортированный префикс

Массив делится на отсортированный префикс слева (сначала это один первый элемент) и остаток справа. Берём первый элемент остатка - ключ - и вставляем его в префикс: идём справа налево по префиксу и, пока встречаем элементы БОЛЬШЕ ключа, сдвигаем их на одну позицию вправо; как только встретили элемент не больше ключа (или дошли до края) - ставим ключ в освободившееся место. Префикс вырос на один. Повторяем n − 1 раз.

Правило

Сортировка вставками вставляет каждый элемент в отсортированный префикс слева, сдвигая большие вправо. Худший случай (вход задом наперёд) - Θ(n²); лучший (почти упорядоченный) - Θ(n), потому что сдвигать почти нечего. Она АДАПТИВНА (цена падает с упорядоченностью входа), УСТОЙЧИВА (равные сохраняют порядок) и работает на месте. Это лучшая из простых сортировок и рабочая лошадка на маленьких и почти упорядоченных массивах.

Разбор: почему на почти упорядоченных данных это Θ(n)

Вся работа вставки - во внутреннем сдвиге: сколько элементов префикса больше ключа, столько сдвигов. Если массив уже отсортирован, то каждый новый ключ не меньше всего префикса - внутренний цикл сразу видит, что сдвигать нечего, и делает 0 сдвигов. Остаётся только n − 1 внешних шагов и по одному сравнению на каждый - Θ(n). Если массив ПОЧТИ упорядочен (каждый элемент не дальше k позиций от своего места), то каждый ключ сдвигает не больше k элементов - всего Θ(n·k), и при маленьком k это практически линия. Вот формальный смысл слов «выигрывает на почти упорядоченных»: её цена - не константа n², а величина, пропорциональная БЕСПОРЯДКУ во входе (числу пар, стоящих не по порядку). Мало беспорядка - мало работы.

Разбор: худший случай и устойчивость

Худший вход - строго убывающий, например [5, 4, 3, 2, 1]. Тогда каждый новый ключ меньше всего префикса и проваливается в самое начало, сдвигая ВЕСЬ префикс: сдвигов 1 + 2 + ... + (n−1) = Θ(n²). Это потолок. Теперь про устойчивость: во внутреннем цикле мы сдвигаем элементы СТРОГО большие ключа (> ключ), а на равном (= ключ) останавливаемся и ставим ключ ПОСЛЕ него. Значит два равных элемента никогда не перепрыгнут друг через друга - их взаимный порядок сохранится. Это и есть устойчивость, и держится она на одном знаке: сравнивать надо >, а не ≥. Поставь ≥ - сортировка останется верной, но потеряет устойчивость (равные будут меняться местами).

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

Первая ошибка - взять ≥ вместо > во внутреннем сравнении и молча потерять устойчивость: массив отсортируется верно, но равные элементы поменяются местами, и это всплывёт позже, когда устойчивость окажется нужна (сортировка по второму ключу - см. последнюю главу). Вторая - считать сортировку вставками «просто ещё одним квадратом» и не пользоваться её адаптивностью: именно из-за неё вставками сортируют маленькие куски внутри быстрых сортировок и почти готовые данные. Третья - применить её к большому СЛУЧАЙНОМУ массиву: там беспорядок максимален, и Θ(n²) бьёт в полную силу.

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

Сортировка вставками живёт внутри промышленных сортировок. Быстрая сортировка и сортировка слиянием на маленьких подмассивах (обычно ≤ 10-20 элементов) переключаются именно на вставки: у неё крохотные накладные расходы, а на коротком куске квадрат неважен. Алгоритм Timsort (стандартная сортировка в Python и Java для объектов) построен вокруг того, что реальные данные ЧАСТО почти упорядочены: он ищет уже упорядоченные куски и сшивает их, а короткие досортировывает вставками - и на почти готовых данных выходит близко к Θ(n). То есть адаптивность вставки - не academic курьёз, а причина, по которой стандартная сортировка так быстра на реальных, почти упорядоченных входах.

Теперь сам

Сравни, сколько СДВИГОВ сделает сортировка вставками на [1, 2, 3, 4] и на [4, 3, 2, 1]. Почему разница именно такая и как это связано со словом «адаптивная»?