Сорт коктейльного шейкера

Сорт коктейльного шейкера

Сорт	Алгоритм сортировки
Структура данных	Множество
Худшая производительность	$O(n^{2})\,$
Лучшая производительность	$O(n)\,$
Средняя производительность	$O(n^{2})\,$
Наихудшая пространственная сложность	$O(1)$
Оптимальный	Нет

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

Как и большинство вариантов сортировки пузырьком, сортировка шейкером используется в первую очередь в качестве образовательного инструмента. Более производительные алгоритмы, такие как быстрая сортировка , сортировка слиянием или временная сортировка , используются библиотеками сортировки, встроенными в популярные языки программирования, такие как Python и Java.

Псевдокод

Самая простая форма каждый раз проходит по всему списку:

procedure cocktailShakerSort(A : list of sortable items) is
    do
        swapped := false
        for each i in 0 to length(A) − 1 do:
            if A[i] > A[i + 1] then // test whether the two elements are in the wrong order
                swap(A[i], A[i + 1]) // let the two elements change places
                swapped := true
            end if
        end for
        if not swapped then
            // we can exit the outer loop here if no swaps occurred.
            break do-while loop
        end if
        swapped := false
        for each i in length(A) − 1 to 0 do:
            if A[i] > A[i + 1] then
                swap(A[i], A[i + 1])
                swapped := true
            end if
        end for
    while swapped // if no elements have been swapped, then the list is sorted
end procedure

Первый проход вправо сдвинет самый большой элемент на правильное место в конце, а следующий проход влево сдвинет наименьший элемент на правильное место в начале. Второй полный проход переместит второй по величине и второй по величине элементы на правильные места и так далее. После прохождения i первый и последний i элементы в списке оказываются на своих правильных позициях, и их не нужно проверять. Сокращая часть списка, которая каждый раз сортируется, количество операций можно сократить вдвое (см. пузырьковую сортировку ).

Это пример алгоритма в MATLAB/OCTAVE с оптимизацией запоминания последнего индекса подкачки и обновления границ.

function A = cocktailShakerSort(A)
% `beginIdx` and `endIdx` marks the first and last index to check
beginIdx = 1;
endIdx = length(A) - 1;
while beginIdx <= endIdx
    newBeginIdx = endIdx;
    newEndIdx = beginIdx;
    for ii = beginIdx:endIdx
        if A(ii) > A(ii + 1)
            [A(ii+1), A(ii)] = deal(A(ii), A(ii+1));
            newEndIdx = ii;
        end
    end

    % decreases `endIdx` because the elements after `newEndIdx` are in correct order
    endIdx = newEndIdx - 1;

    for ii = endIdx:-1:beginIdx
        if A(ii) > A(ii + 1)
            [A(ii+1), A(ii)] = deal(A(ii), A(ii+1));
            newBeginIdx = ii;
        end
    end
    % increases `beginIdx` because the elements before `newBeginIdx` are in correct order
    beginIdx = newBeginIdx + 1;
end
end

Отличия от пузырьковой сортировки

Сортировка шейкером — это небольшая разновидность пузырьковой сортировки . Отличается тем, что вместо многократного прохождения по списку снизу вверх, он проходит поочередно снизу вверх, а затем сверху вниз. Он может обеспечить немного лучшую производительность, чем стандартная пузырьковая сортировка. Причина этого в том, что пузырьковая сортировка проходит по списку только в одном направлении и, следовательно, может перемещать элементы назад только на один шаг за каждую итерацию.

Примером списка, доказывающего эту точку зрения, является список (2,3,4,5,1), которому нужно будет пройти только один проход коктейльной сортировки, чтобы его отсортировать, но при использовании восходящей пузырьковой сортировки потребуется четыре проходит. Однако один проход сортировки коктейля следует засчитывать как два прохода сортировки пузырьком. Обычно коктейльная сортировка выполняется менее чем в два раза быстрее, чем пузырьковая.

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

Сложность

Сложность сортировки шейкера для коктейлей в обозначении большой О составляет $O(n^{2})$ как для худшего случая, так и для среднего случая, но он становится ближе к $O(n)$ если список в основном упорядочен перед применением алгоритма сортировки. Например, если каждый элемент находится в позиции, которая отличается не более чем на k (k ≥ 1) от позиции, в которой он окажется в конечном итоге, сложность сортировки шейкером становится $O(kn).$

Сортировка шейкером также кратко обсуждается в книге «Искусство компьютерного программирования» , наряду с аналогичными усовершенствованиями сортировки пузырьком. В заключение Кнут рассказывает о пузырьковой сортировке и ее улучшениях:

Но ни одно из этих усовершенствований не приводит к созданию алгоритма лучше, чем прямая вставка [то есть сортировка вставкой ]; что прямая вставка не подходит для больших N. и мы уже знаем , [...] Короче говоря, пузырьковая сортировка, похоже, не дает никаких рекомендаций, кроме запоминающегося названия и того факта, что она приводит к некоторым интересным теоретическим проблемам.

— Д. Э. Кнут

Источники

• Хартенштейн, Р. (июль 2010 г.). «Новая мировая модель вычислений» (PDF) . Великая задача по переосмыслению вычислений . Белу-Оризонти , Бразилия: CSBC. Архивировано из оригинала (PDF) 7 августа 2013 г. Проверено 14 января 2011 г.

Внешние ссылки

• Интерактивная демонстрация коктейля
• Исходный код Java и анимированная демонстрация коктейльной сортировки (так называемой двунаправленной пузырьковой сортировки) и некоторых других алгоритмов.
• «.NET реализация сортировки коктейлей и некоторых других алгоритмов» . Архивировано из оригинала 12 февраля 2012 г.