Шейкерная сортировка (перемешиванием) .

Рассматриваемый в данной статье алгоритм имеет несколько непохожих друг на друга названий. Среди них: сортировка перемешиванием, двунаправленная пузырьковая сортировка, шейкерная сортировка, пульсирующая сортировка (ripple sort), трансфертная сортировка (shuttle sort), и даже сортировка «счастливый час» (happy hour sort).


Второй вариант (двунаправленная пузырьковая сортировка) наиболее точно описывает процесс работы алгоритма. Здесь, в его название, довольно-таки удачно включен термин «пузырьковая». Это действительно альтернативная версия известного метода, модификации в котором заключаются, по большей части, в реализации, упомянутой в названии, двунаправленности: алгоритм перемещается, ни как в обменной (пузырьковой) сортировке – строго снизу вверх (слева направо), а сначала снизу вверх, потом сверху вниз.

Перестановка элементов в шейкерной сортировке выполняется аналогично той же в пузырьковой сортировке, т. е. два соседних элемента, при необходимости, меняются местами. Пусть массив требуется упорядочить по возрастанию. Обозначим каждый пройденный путь от начала до конца последовательности через Wi, где i – номер пути; а обратный путь (от конца к началу) через —Wj, где j – номер пути.

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

Код программы на C++:

Код программы на Pascal:

 

Следующая таблица отражает временную сложность алгоритма шейкерной сортировки для трех случаев.

Лучший случай

Средний случай

Наихудший случай

O(n)

O(n2)

O(n2)

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


Похожие записи:

Оставить комментарий

Ваш e-mail не будет опубликован. Обязательные поля отмечены *