Введение
Алгоритм сортировки
Сортировка «коктейльный шейкер», также известная как двунаправленная сортировка пузырьком, коктейльная сортировка, шейкерная сортировка (которая также может относиться к варианту сортировки выбором), сортировка «рябь», сортировка «перемешивание» или сортировка «челнок», является расширением сортировки пузырьком. Алгоритм расширяет сортировку пузырьком, работая в двух направлениях. Хотя он улучшает сортировку пузырьком, быстрее перемещая элементы в начало списка, он обеспечивает лишь незначительное повышение производительности. Как и большинство вариантов сортировки пузырьком, сортировка «коктейльный шейкер» используется в основном в качестве учебного пособия. Более производительные алгоритмы, такие как быстрая сортировка, сортировка слиянием или сортировка TimSort, используются в библиотеках сортировки, встроенных в популярные языки программирования, такие как Python и Java.
Отличия от сортировки пузырьками
Коктейль-шейкер — это небольшая разновидность сортировки пузырьком. Он отличается тем, что вместо многократного прохода по списку снизу вверх, он проходит попеременно снизу вверх, а затем сверху вниз. Это позволяет добиться немного лучшей производительности, чем у стандартной сортировки пузырьком. Причина в том, что сортировка пузырьком проходит по списку только в одном направлении и поэтому может перемещать элементы назад только на один шаг за каждую итерацию. Примером списка, демонстрирующего это, является список (2, 3, 4, 5, 1), который можно отсортировать всего за один проход алгоритмом коктейль-шейкер, в то время как восходящая сортировка пузырьком потребует четыре прохода. Однако один проход коктейль-шейкера следует считать двумя проходами сортировки пузырьком. Как правило, коктейль-шейкер работает менее чем в два раза быстрее сортировки пузырьком. Дополнительной оптимизацией может служить запоминание алгоритмом позиции последнего фактического обмена. В следующей итерации обмены за пределами этой позиции не будут выполняться, что сократит длину проходов. Поскольку коктейль-шейкер работает в обоих направлениях, диапазон возможных обменов, то есть область проверки, уменьшается с каждым проходом, что незначительно снижает общее время выполнения.
Сложность
Сложность сортировки перемешиванием в нотации «большое О» составляет для худшего и среднего случаев, но приближается к , если список в основном отсортирован до применения алгоритма сортировки. Например, если каждый элемент находится на расстоянии не более k (k ≥ 1) от своей конечной позиции, сложность сортировки перемешиванием становится .
Сортировка перемешиванием также кратко рассматривается в книге «Искусство программирования», наряду с аналогичными улучшениями сортировки пузырьком. В заключение Кнут отмечает о сортировке пузырьком и её усовершенствованиях: