Comb Sort

Проблема

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

Решение

Алгоритм начинает с промежутка (gap), примерно равного длине массива, и сравнивает элементы, отстоящие друг от друга на этот gap, меняя их местами при необходимости. После каждого прохода gap уменьшается делением на фиксированный коэффициент (обычно 1.3). Когда gap становится равным 1, алгоритм превращается в обычный bubble sort, но к этому моменту большинство «черепах» уже переставлены на большое расстояние за один шаг, поэтому финальные проходы короткие.

Как это работает

Заявление «gap большой - элементы прыгают далеко» стоит проверить на конкретных числах. Возьмём массив [2, 3, 4, 5, 6, 7, 8, 9, 10, 1] (n = 10) - классическая «черепаха», единица, стоит на самом последнем месте.

Начальный gap = 10. После первого деления на 1.3: gap = floor(10 / 1.3) = 7. Проход сравнивает i и i + 7 для i = 0, 1, 2. При i = 2 сравниваются a[2] = 4 и a[9] = 1 - перестановка отправляет 1 сразу на позицию 2. Единица переместилась на 7 позиций за одно сравнение - в обычном bubble sort на такое расстояние ушло бы 7 отдельных проходов.

Прослеживая дальше: gap уменьшается по цепочке 7 → 5 → 3 → 2 → 1. Единица остаётся на позиции 2 через проходы с gap 5 и 3 (её партнёры по сравнению на этих промежутках больше неё), а на проходе с gap = 2 сравнение a[0] и a[2] отправляет её на позицию 0 - на своё финальное место она попадает всего за 4 прохода, а не за 9, как потребовалось бы обычному bubble sort для той же стартовой позиции.

Алгоритм в целом завершается за 6 проходов на этом входе: gap = 7, 5, 3, 2, 1 (с перестановками), и ещё один финальный проход с gap = 1 без единой перестановки, подтверждающий, что массив готов. Геометрическое убывание gap - в отличие от линейного уменьшения на единицу в bubble sort - и даёт этот выигрыш в константе: число проходов растёт как log₁.₃(n), а не как n.

Это не превращает алгоритм в O(n log n) в строгом смысле - каждый проход с малым gap всё ещё стоит O(n) сравнений, а на враждебно построенных входах быстрый спуск gap может не успеть развести все инверсии до перехода к gap = 1, и тогда финальные проходы деградируют к полноценному bubble sort - отсюда и худший случай O(n²), совпадающий с bubble sort.

Есть известная слабость именно коэффициента 1.3: элементы, отстоящие ровно на 9 или 10 позиций в определённых паттернах, могут пережить всю цепочку сжатий gap и остаться неотсортированными до самого прохода с gap = 1. Модификация Combsort11 решает это точечно: если очередной gap оказывается равен 9 или 10, он принудительно заменяется на 11 - небольшая эмпирическая заплатка поверх и без того эмпирического коэффициента 1.3.

Сортировку расчёской изобрёл Влодзимеж Добосевич (Włodzimierz Dobosiewicz) в 1980 году, но она осталась малоизвестной до 1991-го, когда Стивен Лейси и Ричард Бокс заново описали её в статье «A Fast, Easy Sort» в журнале Byte Magazine - именно они экспериментально подобрали коэффициент 1.3 как оптимальный баланс между скоростью сжатия gap и качеством перемешивания, протестировав алгоритм на массивах разного размера.

Итог: выигрыш сортировки расчёской - это константный множитель от геометрического сжатия gap, а не смена асимптотического класса. Она остаётся полезной как учебный мостик к сортировке Шелла, которая применяет ту же идею убывающего gap не к обмену соседей, а к вставке - и как таковая, к более серьёзному сокращению числа сравнений в среднем случае.

Нюансы выбора

Почти всегда вместо bubble sort - реализация отличается на несколько строк (gap вместо фиксированного соседства), а выигрыш в константе заметен уже на массивах от нескольких сотен элементов.

Против сортировки Шелла - если важна более предсказуемая производительность на случайных данных, Shell sort с хорошей последовательностью gap (например, Chiba/Sedgewick) обычно обгоняет comb sort; выбирайте comb sort только когда важна простота одной операции - обмена, а не вставки.

Не выбирать при известном враждебном или структурированном входе - если входные данные могут быть подобраны злонамеренно или содержат регулярные паттерны, риск попасть в O(n²) реален; для гарантий стоит взять merge sort, heap sort или хотя бы Combsort11.

Как шаг перед сортировкой Шелла в учебном курсе - объяснить сначала, что убывающий gap с простым обменом соседей уже даёт заметный выигрыш, а затем показать, что тот же gap, применённый к вставке, даёт ещё более сильный алгоритм.

Примеры в коде

Технический отчёт Влодзимежа Добосевича (1980) - первое описание идеи сравнений через убывающий gap поверх пузырьковой сортировки, задолго до того, как алгоритм получил своё нынешнее имя.

«A Fast, Easy Sort» Стивена Лейси и Ричарда Бокса (Byte Magazine, апрель 1991) - статья, заново популяризировавшая алгоритм под именем «comb sort» среди хобби-программистов начала 1990-х и предложившая коэффициент сжатия 1.3 на основе собственных тестов.

Combsort11 - широко цитируемая модификация, форсирующая gap в 11 вместо 9 или 10, встречается в справочных реализациях и обсуждениях как стандартная защита от известного класса плохо сортируемых входов при коэффициенте 1.3.

Курсы по алгоритмам сортировки, сравнивающие семейство «убывающего gap» (comb sort, Shell sort), используют именно эту пару как пример того, что одна и та же идея (сравнение не только соседей) даёт разный выигрыш в зависимости от того, к какой базовой операции - обмену или вставке - она применяется.

Когда применять

• Как быстрая замена пузырьковой сортировке, когда простота кода важнее гарантированной сложности O(n log n).
• Для обучения идее «сжимающегося gap» перед переходом к сортировке Шелла, которая использует тот же принцип для вставок.

Примеры из практики

• Игровые движки и небольшие утилиты, где нужно быстро улучшить существующую реализацию bubble sort без переписывания на другой алгоритм с нуля.
• Учебные материалы по оптимизации алгоритмов - классический пример того, как небольшое изменение (gap вместо соседей) убирает конкретный класс худших случаев.