Сорт шейкера для коктейлей

Сорт шейкера для коктейлей

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

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

Как и большинство вариантов пузырьковой сортировки, сортировка шейкером используется в основном как образовательный инструмент. Более эффективные алгоритмы, такие как быстрая сортировка , сортировка слиянием или timsort, используются библиотеками сортировки, встроенными в популярные языки программирования, такие как Python и Java. ^{[4] [5]}

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

процедура cocktailShakerSort(A : список сортируемых элементов ) выполняется  поменяно местами := false для каждого i от 0 до length(A) − 1 do:  if A[i] > A[i + 1] then  // проверить, находятся ли два элемента в неправильном порядке swap(A[i], A[i + 1]) // позволить двум элементам поменяться местами поменял местами := правда конец если  конец для  если не поменялось тогда  // мы можем выйти из внешнего цикла здесь, если не произошло никаких обменов.  break do-while loop  end if поменяно местами := false для каждого i в length(A) − 1 до 0 сделать:  если A[i] > A[i + 1] , то поменять местами(A[i], A[i + 1]) поменял местами := правда end if  end for  while swapped // если ни один элемент не был поменян, то список сортируется end procedure

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

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

function  A = cocktailShakerSort ( A ) % `beginIdx` и `endIdx` отмечают первый и последний индекс для проверки 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                                      % уменьшает `endIdx`, поскольку элементы после `newEndIdx` находятся в правильном порядке endIdx = newEndIdx - 1 ;      для ii = endIdx : - 1 : beginIdx если A ( ii ) > A ( ii + 1 ) [ A ( ii + 1 ), A ( ii )] = deal ( A ( ii ), A ( ii + 1 )); newBeginIdx = ii ; конец конец % увеличивает `beginIdx`, потому что элементы перед `newBeginIdx` находятся в правильном порядке beginIdx = newBeginIdx + 1 ; конец конец                         

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

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

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

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

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

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

—  Д. Э. Кнут ^[1]

• Двойная сортировка «Шейкер» — это вариант сортировки «Шейкер», которая выполняет прямой и обратный проход на каждой итерации одновременно, что повышает производительность по сравнению с оригиналом.

• Hartenstein, R. (июль 2010 г.). "Новая мировая модель вычислений" (PDF) . Грандиозный вызов переосмыслению вычислений . Белу-Оризонти , Бразилия: CSBC. Архивировано из оригинала (PDF) 2013-08-07 . Получено 2011-01-14 .

Реализация алгоритма Wikibook имеет страницу на тему: Сортировка коктейлем

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