Шейкерная сортировка (Двунаправленная пузырьковая сортировка, Shaker Sort (bidirectional bubble sort))

Шейкерная сортировка (Shaker Sort), она же двунаправленная пузырьковая сортировка (bidirectional bubble sort), является алгоритмом сортировки, который представляет собой модификацию классического пузырькового метода. Он работает по принципу перемещения элементов в обе стороны (вверх и вниз) по массиву, что позволяет более эффективно упорядочивать данные.

▎Принцип работы Shaker Sort

1. Два прохода: Алгоритм выполняет два прохода по массиву: один — слева направо, другой — справа налево.

2. Слева направо: На первом проходе алгоритм сравнивает соседние элементы и меняет их местами, если они находятся в неправильном порядке (больший элемент слева от меньшего). Этот проход "поднимает" наибольший элемент в конец массива.

3. Справа налево: На втором проходе алгоритм снова сравнивает соседние элементы, но теперь идет справа налево, "опуская" наименьший элемент в начало массива.

4. Повторение: Процессы продолжаются до тех пор, пока не будет выполнен полный проход без каких-либо перестановок, что означает, что массив отсортирован.

▎Временная сложность

• Лучший случай: O(n) — когда массив уже отсортирован.

• Средний и худший случай: O(n²) — как и у обычного пузырькового метода.

• Худший случай: O(n²) - обратно отсортированный массив

▎Пространственная сложность

O(1) - алгоритм сортирует массив "на месте".

▎Устойчивость:

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

Реализация сортировки на языке программирования C++:

Реализация алгоритма на Python: