Cocktail Shaker Sort

Проблема

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

Решение

Алгоритм чередует направление прохода: сначала идёт слева направо, как обычный bubble sort, выталкивая наибольший элемент в конец; затем сразу разворачивается и идёт справа налево, выталкивая наименьший элемент в начало. Границы отсортированной части сжимаются с обеих сторон одновременно, поэтому «черепахи» устраняются так же быстро, как и «кролики» (большие элементы у начала массива).

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

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

В обычном bubble sort этот 1 сдвигается влево ровно на одну позицию за каждый проход - алгоритму нужно 9 полных проходов, чтобы дотащить его до индекса 0. В шейкерной сортировке первый проход слева направо просто переставляет 10 и 1 местами ([2,3,4,5,6,7,8,9,1,10]), а следующий сразу же проход справа налево тащит 1 через всю оставшуюся зону за один присест - единица оказывается в начале уже после 2 проходов вместо 9.

Это не совпадение, а асимметрия, изначально заложенная в bubble sort. «Кролик» (большой элемент у начала массива) уже движется быстро в обычном одностороннем проходе: сравнение a[i] > a[i+1] заставляет его сдвигаться вправо на каждом шаге того же прохода, так что он долетает до своего места за один проход. Медленно ползёт только «черепаха» - потому что после того как её один раз сдвинули влево, проход уже ушёл дальше вправо и не возвращается проверить её снова. Шейкерная сортировка - это, по сути, патч именно для этого одностороннего слепого пятна, а не общее ускорение алгоритма.

Отсюда же следует, почему средний и худший случай остаются O(n²). Каждый полный двойной проход сжимает зону с обеих сторон: end-- после левого прохода и start++ после правого. Значит, всего может быть не больше ⌈n/2⌉ двойных проходов, а k-й проход обрабатывает зону шириной примерно n - 2k с обеих сторон - 2(n - 2k) сравнений. Просуммировав по всем k от 0 до n/2, получаем порядка n²/2 сравнений - та же величина, что и у обычного bubble sort, только переупакованная в проходы вдвое короче, но их вдвое больше по счёту с обеих сторон одновременно.

В коде на этой странице есть тонкая асимметрия в самой проверке swapped. Ранний выход if (!swapped) break стоит только после левого прохода - если он ничего не переставил, правый проход вообще не запускается. После правого прохода отдельной проверки нет: цикл просто идёт на следующую итерацию while (swapped), и если правый проход тоже ничего не поменял, флаг остаётся false, и цикл завершается сам собой на условии while. Итог тот же самый - лишний проход не выполняется в обоих случаях, - но механизм выхода технически разный: явный break против естественного условия цикла.

Имя «shaker sort» само по себе неоднозначно и часто путает при чтении разных источников. Помимо двунаправленной пузырьковой сортировки, описанной здесь, тот же термин иногда используют для совсем другого алгоритма - двунаправленного варианта selection sort, который за один проход одновременно находит и минимум, и максимум оставшейся неотсортированной зоны и сразу ставит оба на края. Эти два алгоритма решают внешне похожую задачу (обработать оба конца массива за один заход), но устроены принципиально по-разному: один основан на перестановке соседей, второй - на поиске экстремума.

Более серьёзное решение той же проблемы «черепах» - comb sort, изобретённый Влодзимежем Добосевичем в 1980 году и заново популяризированный Стивеном Лейси и Ричардом Боксом в статье в журнале Byte в 1991-м. Вместо смены направления comb sort сравнивает элементы через зазор шире 1, сокращая его на каждом проходе (обычно делением на 1.3) - это сразу расталкивает «черепах» на большие расстояния, а не тащит их пошагово в обратную сторону, поэтому даёт заметно лучшую константу, оставаясь при этом в том же классе O(n²) в худшем случае.

Итог: шейкерная сортировка стоит рассматривать не как «улучшенный bubble sort» в общем смысле, а как точечный патч под одну конкретную форму входных данных - редкие элементы, застрявшие не с той стороны. Как учебная концепция она ценна тем, что показывает: изменение стратегии обхода (направление, зазор) может радикально поменять поведение на конкретных распределениях, не трогая при этом асимптотику в общем случае - мостик к пониманию, зачем вообще нужны более сложные стратегии вроде divide-and-conquer у merge/quick sort.

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

Против comb sort - если реальная цель именно быстро устранить черепах, comb sort справляется с этим лучше за счёт сокращающегося зазора, а не смены направления; шейкерная сортировка выигрывает только простотой объяснения механизма, а не производительностью.

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

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

Не выбирать для случайных или крупных данных - ни асимметрия направления, ни early-exit флаг не спасают от O(n²) сравнений на случайном входе; для этого нужны quicksort, mergesort или Timsort, а не патчи над bubble sort.

Если нужно меньше перестановок, а не меньше проходов - двунаправленный вариант selection sort (иногда тоже называемый «shaker sort», см. выше) ищет min и max за один проход и переставляет каждый элемент максимум один раз за операцию, тогда как здесь любая перестановка - это отдельный своп соседей.

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

Wikipedia и большинство вводных курсов по алгоритмам используют именно эту пару bubble/cocktail shaker sort как канонический пример того, что изменение стратегии обхода может радикально поменять поведение на конкретной форме входных данных, не меняя асимптотику в общем случае - урок важнее самого алгоритма.

Comb sort (Влодзимеж Добосевич, 1980; заново описан Стивеном Лейси и Ричардом Боксом в Byte Magazine, 1991) - самостоятельный алгоритм, решающий ту же проблему черепах через сокращающийся зазор, а не смену направления; исторически применялся в нескольких ранних библиотеках сортировки как быстрая и простая замена bubble sort до широкого распространения quicksort.

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

Прошивки для маленьких микроконтроллеров, где важен размер скомпилированного кода, а не асимптотика: шейкерная сортировка требует лишь на несколько строк больше, чем bubble sort, но не тянет за собой ни рекурсию, ни дополнительные структуры данных, которых требуют более быстрые алгоритмы вроде quicksort.

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

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

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

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