Шейкерная СортировкаCocktail Shaker Sort

Поддерживается сужающееся "рабочее окно" [lo, hi] — снаружи него элементы уже на своих финальных местах. Проход слева направо по [lo, hi] переставляет соседей не по порядку (как в bubble sort) — по его завершении максимум окна гарантированно оказался в позиции hi, и hi уменьшается на 1. Симметричный проход справа налево по новому [lo, hi] точно так же гарантированно доносит минимум окна до позиции lo, и lo увеличивается на 1. Если за проход в любую сторону не произошло ни одной перестановки — массив уже отсортирован, и можно остановиться раньше, не дожидаясь, пока окно схлопнется до пустого.A shrinking "working window" [lo, hi] is maintained — outside it, elements are already in their final spots. A left-to-right pass over [lo, hi] swaps out-of-order neighbors (like bubble sort) — by its end, the window's maximum is guaranteed to be at position hi, and hi decreases by 1. A symmetric right-to-left pass over the new [lo, hi] equally guarantees the window's minimum lands at position lo, and lo increases by 1. If either pass makes no swaps at all, the array is already sorted, and the loop can stop early instead of waiting for the window to collapse to empty.

void cocktail_shaker_sort(std::vector<int>& a) {
    int lo = 0, hi = (int)a.size() - 1;
    bool swapped = true;
    while (swapped) {
        swapped = false;
        for (int i = lo; i < hi; ++i)           // проход вправо// rightward pass
            if (a[i] > a[i + 1]) { std::swap(a[i], a[i + 1]); swapped = true; }
        if (!swapped) break;
        --hi;
        swapped = false;
        for (int i = hi; i > lo; --i)           // проход влево// leftward pass
            if (a[i - 1] > a[i]) { std::swap(a[i - 1], a[i]); swapped = true; }
        ++lo;
    }
}

Синяя рамка — текущее рабочее окно [lo, hi]. Стрелка в логе показывает направление текущего прохода. Зелёная заливка — элементы, уже вышедшие за пределы окна (на финальных местах).The blue outline is the current working window [lo, hi]. The log's arrow shows the current pass direction. Green fill marks elements already outside the window (in their final spots).

Асимптотика в худшем и среднем случае остаётся Θ(n²) — та же, что у bubble sort, потому что число сравнений на массиве общего положения не меняется от смены направления. Выигрыш конкретный и ограниченный: устраняется конкретный патологический случай "черепахи у левого края" ([2, 3, 4, ..., n, 1] — маленький элемент почти в конце требует n-1 проходов обычного bubble sort, а шейкерной сортировке хватает одного обратного прохода). На случайных данных практический выигрыш умеренный — обычно в 1.5-2 раза меньше сравнений, не смена класса сложности.Worst- and average-case asymptotics stay Θ(n²) — the same as bubble sort, because the number of comparisons on a general-position array doesn't change with the direction switch. The gain is specific and bounded: it eliminates a particular pathological case, "turtles near the left edge" ([2, 3, 4, ..., n, 1] — a small element almost at the end needs n-1 passes of plain bubble sort, while shaker sort needs just one reverse pass). On random data the practical gain is modest — typically 1.5-2x fewer comparisons, not a change of complexity class.