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

1.

Омск 2020
ШЕЙКЕРНАЯ СОРТИРОВКА
(ПЕРЕМЕШИВАНИЕМ)
Выполнил(а): студент гр. ПИб20-И2
Бернгардт Геннадий Сергеевич
Проверил: доцент кафедры ПИЭ
Пестова Светлана Юрьевна
Омск 2020

2.

Шейкерная сортировка (cocktail sort, shaker sort),
или сортировка перемешиванием - усовершенствованная
разновидность сортировки пузырьком, при
которой сортировка производиться в двух направлениях,
меняя направление при каждом проходе.

3.

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

4.

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

5.

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

6.

Примеры записи кода:
Код программы на C++

7.

Примеры записи кода:
Код программы на Pascal

8.

Спасибо за внимание!