Сорт коктейльный шейкер - Cocktail shaker sort

Сорт коктейльный шейкер
Визуализация сортировки шейкер
КлассАлгоритм сортировки
Структура данныхМассив
Худший случай спектакль
Лучший случай спектакль
Средний спектакль
Худший случай космическая сложность

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

Как и большинство разновидностей пузырьковой сортировки, сортировка с помощью шейкер-коктейля используется в первую очередь как обучающий инструмент. Более производительные алгоритмы, такие как Timsort, или Сортировка слиянием используются библиотеками сортировки, встроенными в популярные языки программирования, такие как Python и Java.[4][5]

Псевдокод

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

процедура cocktailShakerSort (A : список сортируемых элементов) является    делать        поменяно местами: = ложь для каждого я в 0 к длина (А) - 2 делать:            если A [i]> A [i + 1] тогда // проверяем, находятся ли два элемента в неправильном порядке                своп (A [i], A [i + 1]) // позволяем двум элементам поменяться местами                поменяно местами: = true конец, если        конец для        если не поменяны местами тогда            // здесь можно выйти из внешнего цикла, если свопов не было.            прервать цикл do-while        конец, если        поменяно местами: = ложь для каждого я в длина (А) - 2 к 0 делать:            если A [i]> A [i + 1] тогда                swap (A [i], A [i + 1]) swapped: = true конец, если        конец для    в то время как поменяны местами // если ни один элемент не поменялся местами, то список сортируетсяконец процедуры

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

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

функцияА =коктейльШейкерСортировать(А)% `beginIdx` и` endIdx` обозначают первый и последний индекс для проверкиbeginIdx = 1;endIdx = длина(А) - 1;в то время как beginIdx <= endIdx    newBeginIdx = endIdx;    newEndIdx = beginIdx;    для ii = beginIdx: endIdx        если A (ii)> A (ii + 1)            [А(ii+1), А(ii)] = по рукам(А(ii), А(ii+1));            newEndIdx = ii;        конецконец    % уменьшает endIdx, потому что элементы после newEndIdx расположены в правильном порядке    endIdx = newEndIdx - 1;    для ii = endIdx: -1: beginIdx        если A (ii)> A (ii + 1)            [А(ii+1), А(ii)] = по рукам(А(ii), А(ii+1));            newBeginIdx = ii;        конецконец    % увеличивает beginIdx, потому что элементы перед newBeginIdx расположены в правильном порядке    beginIdx = newBeginIdx + 1;конецконец

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

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

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

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

Сложность

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

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

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

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

использованная литература

  1. ^ а б c Кнут, Дональд Э. (1973). «Сортировка по обмену». Искусство программирования. 3. Сортировка и поиск (1-е изд.). Эддисон-Уэсли. С. 110–111. ISBN  0-201-03803-X.
  2. ^ Блэк, Пол Э .; Бокхольт, Боб (24 августа 2009 г.). «двунаправленная пузырьковая сортировка». В черном, Пол Э. (ред.). Словарь алгоритмов и структур данных. Национальный институт стандартов и технологий. Архивировано из оригинал 16 марта 2013 г.. Получено 5 февраля 2010.
  3. ^ Duhl, Мартин (1986). "Die schrittweise Entwicklung und Beschreibung einer Shuffle-Sort-Array Schaltung". HYPERKARL aus der Algorithmischen Darstellung des BUBBLE-SORT-ALGORITHMUS. Projektarbeit (на немецком). Технический университет Кайзерслаутерна.
  4. ^ "[JDK-6804124] (coll) Заменить" измененную сортировку слиянием "в java.util.Arrays.sort на timsort - Система ошибок Java". bugs.openjdk.java.net. Получено 2020-01-11.
  5. ^ Питерс, Тим (2002-07-20). "[Python-Dev] Сортировка". Получено 2020-01-11.

Источники

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