 | |
| Учебный класс | Алгоритм сортировки |
|---|---|
| Структура данных | Множество |
| Наихудшая производительность | |
| Лучшая производительность | |
| Средняя производительность | |
| Сложность пространства в наихудшем случае | |
Шейкер рода , [1] , также известный как двунаправленного пузырьковой сортировки , [2] коктейль рода , шейкер рода (который может также относиться к варианту выбора рода ), пульсации рода , перетасовать рода , [3] или шатл рода , является расширение пузырьковой сортировки . Алгоритм расширяет пузырьковую сортировку, работая в двух направлениях. Хотя он улучшает пузырьковую сортировку за счет более быстрого перемещения элементов в начало списка , он обеспечивает лишь незначительное улучшение производительности.
Как и большинство вариантов пузырьковой сортировки, сортировка с помощью шейкер-коктейля используется в первую очередь как обучающий инструмент. Более производительные алгоритмы, такие как временная сортировка или сортировка слиянием , используются библиотеками сортировки, встроенными в популярные языки программирования, такие как Python и Java. [4] [5]
Псевдокод [ править ]
Самая простая форма каждый раз проходит через весь список:
процедура cocktailShakerSort (A : список сортируемых элементов) : do поменяно местами: = ложь для каждого i в 0 до длины (A) - 2 делать: если A [i]> A [i + 1], то // проверяем, находятся ли два элемента в неправильном порядке поменять местами (A [i], A [i + 1]) // пусть два элемента поменяются местами поменяно местами: = истина end if end for if not swappped then // мы можем выйти из внешнего цикла здесь, если свопы не произошли. break do-while loop end if поменяно местами: = ложь для каждого I в длине (A) - 2 до 0 делать: если А [я]> А [г + 1] , то своп (A [i], A [i + 1]) поменяно местами: = истина end if end for while swapped // если никакие элементы не были заменены местами, то список отсортирован end procedure
Первый проход вправо сдвинет самый большой элемент на его правильное место в конце, а следующий проход влево сдвинет самый маленький элемент на его правильное место в начале. Второй полный проход сдвинет второй по величине и второй по величине элементы на их правильные места и так далее. После прохождения i первые i и последние i элементы в списке занимают свои правильные позиции и не нуждаются в проверке. Укорачивая часть списка, которая сортируется каждый раз, количество операций может быть уменьшено вдвое (см. Пузырьковая сортировка ).
Это пример алгоритма в MATLAB / OCTAVE с оптимизацией запоминания последнего индекса подкачки и обновления границ.
функция A = cocktailShakerSort ( A ) % `beginIdx` и` endIdx` обозначают первый и последний индексы для проверкиbeginIdx = 1 ; endIdx = длина ( A ) - 1 ; а beginIdx <= endIdx newBeginIdx = endIdx ; newEndIdx = beginIdx ; для ii = beginIdx : endIdx если A ( ii ) > A ( ii + 1 ) [ A ( ii + 1 ), A ( ii )] = сделка ( A ( ii ), A ( ii + 1 )); newEndIdx = ii ; конец конец % уменьшает endIdx, потому что элементы после newEndIdx расположены в правильном порядке endIdx = newEndIdx - 1 ; для ii = endIdx : - 1 : beginIdx если A ( ii ) > A ( ii + 1 ) [ A ( ii + 1 ), A ( ii )] = сделка ( A ( ii ), A ( ii + 1 )); newBeginIdx = ii ; конец конец % увеличивает beginIdx, потому что элементы перед newBeginIdx расположены в правильном порядке beginIdx = newBeginIdx + 1 ; конецконецОтличия от пузырьковой сортировки [ править ]
Сорт коктейльный шейкер - это небольшая вариация пузырьковой сортировки . [1] Он отличается тем, что вместо многократного прохождения списка снизу вверх, он проходит поочередно снизу вверх, а затем сверху вниз. Он может обеспечить немного лучшую производительность, чем стандартная пузырьковая сортировка. Причина этого в том, что пузырьковая сортировка проходит по списку только в одном направлении и, следовательно, может перемещать элементы назад только на один шаг за каждую итерацию.
Примером списка, подтверждающего эту точку зрения, является список (2, 3, 4, 5, 1), которому нужно было бы пройти только один проход коктейльной сортировки, чтобы стать отсортированным, но если бы использование восходящей пузырьковой сортировки заняло бы четыре проходит. Однако один проход сортировки коктейлей следует засчитывать как два прохода пузырьковой сортировки. Обычно сортировка коктейлей выполняется менее чем в два раза быстрее, чем сортировка пузырьков.
Другая оптимизация может заключаться в том, что алгоритм запоминает, где был произведен последний фактический своп. На следующей итерации не будет никаких свопов сверх этого предела, и алгоритм будет иметь более короткие проходы. Поскольку сортировка в шейкере для коктейлей идет в двух направлениях, диапазон возможных замен, который является диапазоном, который необходимо протестировать, будет уменьшаться за проход, что немного сокращает общее время работы.
Сложность [ править ]
Сложность сортировки шейкер для коктейлей в нотации большой буквы O подходит как для наихудшего случая, так и для среднего случая, но она становится ближе к той, если список в основном упорядочен до применения алгоритма сортировки. Например, если каждый элемент находится в позиции, которая отличается не более чем на k (k ≥ 1) от позиции, в которой он собирается оказаться, сложность сортировки коктейльного шейкера становится
Сортировка с помощью шейкер для коктейлей также кратко обсуждается в книге «Искусство компьютерного программирования» вместе с аналогичными уточнениями пузырьковой сортировки. В заключение Кнут говорит о пузырьковой сортировке и ее улучшениях:
Но ни одно из этих усовершенствований не приводит к алгоритму лучше, чем прямая вставка [то есть сортировка вставкой ]; и мы уже знаем , что прямая вставка не подходит для больших N . [...] Короче говоря, пузырьковой сортировке, похоже, нечего рекомендовать, кроме запоминающегося названия и того факта, что это приводит к некоторым интересным теоретическим проблемам.
- Де Кнут [1]
Ссылки [ править ]
- ^ a b c Кнут, Дональд Э. (1973). «Сортировка по обмену». Искусство программирования . 3. Сортировка и поиск (1-е изд.). Эддисон-Уэсли . С. 110–111. ISBN 0-201-03803-X.
- ↑ Black, Paul E .; Бокхольт, Боб (24 августа 2009 г.). «двунаправленная пузырьковая сортировка». В черном, Пол Э. (ред.). Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий . Архивировано из оригинального 16 марта 2013 года . Проверено 5 февраля 2010 года .
- ^ Duhl, Мартин (1986). "Die schrittweise Entwicklung und Beschreibung einer Shuffle-Sort-Array Schaltung". HYPERKARL aus der Algorithmischen Darstellung des BUBBLE-SORT-ALGORITHMUS . Projektarbeit (на немецком языке). Технический университет Кайзерслаутерна.
- ^ "[JDK-6804124] (coll) Замените" модифицированная сортировка слиянием "в java.util.Arrays.sort на timsort - Система ошибок Java" . bugs.openjdk.java.net . Проверено 11 января 2020 .
- ^ Питерс, Тим (2002-07-20). "[Python-Dev] Сортировка" . Проверено 11 января 2020 .
Источники [ править ]
- Хартенштейн, Р. (июль 2010 г.). «Новая модель мира вычислений» (PDF) . Грандиозный вызов переосмыслению вычислений . Белу-Оризонти , Бразилия: CSBC. Архивировано из оригинального (PDF) 07 августа 2013 года . Проверено 14 января 2011 .
Внешние ссылки [ править ]
 | В реализации алгоритма Викибука есть страница по теме: Сортировка коктейлей |
- Интерактивная демонстрация коктейльной сортировки
- Исходный код Java и анимированная демонстрация коктейльной сортировки (называемой двунаправленной пузырьковой сортировкой) и нескольких других алгоритмов
- «Реализация коктейльной сортировки и некоторых других алгоритмов .NET» . Архивировано из оригинала на 2012-02-12.
