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

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

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

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

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

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

#include "stdafx.h"
#include <iostream>
using namespace std;
//функция обмена
void Swap(int *Mas, int i)
{
int temp;
temp=Mas[i];
Mas[i]=Mas[i-1];
Mas[i-1]=temp;
}
//функция шейкерной сортировки
void ShakerSort(int *Mas, int Start, int N)
{
int Left, Right, i;
Left=Start;
Right=N-1;
while (Left<=Right)
{
for (i=Right; i>=Left; i--)
if (Mas[i-1]>Mas[i]) Swap(Mas, i);
Left++;
for (i=Left; i<=Right; i++)
if (Mas[i-1]>Mas[i]) Swap(Mas, i);
Right--;
}
}
//главная функция
void main()
{
setlocale(LC_ALL,"Rus");
int n, k;
cout<<"Размер массива > "; cin>>n;
int *A=new int[n];
for (k=0; k<n; k++)
{ cout<<k+1<<" элемент > "; cin>>A[k]; }
ShakerSort(A, 1, n);
cout<<"Результирующий массив: ";
for (k=0; k<n; k++)cout<<" "<<A[k];
system("pause>>void");
}

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

program CocktailSort;
uses crt;
type Massiv=array[1..100] of integer;
var
n, k: integer;
A: Massiv;
{процедура шейкерной сортировки}
procedure ShakerSort(Mas: Massiv; Start, m: integer);
var Left, Right, temp, i: integer;
begin
Left:=Start;
Right:=m;
while Left<=Right do
begin
for i:=Right downto Left do
if (Mas[i-1]>Mas[i]) then
begin
temp:=Mas[i];
Mas[i]:=Mas[i-1];
Mas[i-1]:=temp;
end;
Left:=Left+1;
for i:=Left to Right do
if Mas[i-1]>Mas[i] then
begin
temp:=Mas[i];
Mas[i]:=Mas[i-1];
Mas[i-1]:=temp;
end;
Right:=Right-1;
end;
for i:=1 to M do write(' ', Mas[i]);
end;
{основной блок программы}
begin
clrscr;
write('Размер массива > '); read(n);
for k:=1 to n do
begin
write(k, ' элемент > '); read(A[k]);
end;
write('Результирующий массив: ');
ShakerSort(A, 2, n);
end.

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

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