Шейкерная сортировка
Рассматриваемый в данной статье алгоритм имеет несколько непохожих друг на друга названий. Среди них: сортировка перемешиванием, двунаправленная пузырьковая сортировка, шейкерная сортировка, пульсирующая сортировка (ripple sort), трансфертная сортировка (shuttle sort), и даже сортировка «счастливый час» (happy hour sort). Второй вариант (двунаправленная пузырьковая сортировка) наиболее точно описывает процесс работы алгоритма. Здесь, в его название, довольно-таки удачно включен термин «пузырьковая». Это действительно альтернативная версия известного метода, модификации в котором заключаются, по большей части, в реализации, упомянутой в названии, двунаправленности: алгоритм перемещается, ни как в обменной (пузырьковой) сортировке – строго снизу вверх (слева направо), а сначала снизу вверх, потом сверху вниз.
Перестановка элементов в шейкерной сортировке выполняется аналогично той же в пузырьковой сортировке, т. е. два соседних элемента, при необходимости, меняются местами. Пусть массив требуется упорядочить по возрастанию. Обозначим каждый пройденный путь от начала до конца последовательности через Wi, где i – номер пути; а обратный путь (от конца к началу) через -Wj, где j – номер пути. Тогда после выполнения Wi, один из неустановленных элементов будет помещен в позицию справа, как наибольший из еще неотсортированных элементов, а после выполнения -Wj, наименьший из неотсортированных, переместиться в некоторую позицию слева. Так, например, после выполнения W1 в конце массива окажется элемент, имеющий наибольшее значение, а после -W1 в начало отправиться элемент с наименьшим значением.
Код программы на C++:
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() //главная функция
{
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];
}
Код программы на Pascal:
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 {основной блок программы}
write('Размер массива > '); read(n);
for k:=1 to n do
begin
write(k, ' элемент > ');
read(A[k]);
end;
write('Результирующий массив: ');
ShakerSort(A, 2, n);
end.
Следующая таблица отражает временную сложность алгоритма шейкерной сортировки для трех случаев.
| Лучший случай | Средний случай | Наихудший случай |
| O(n) | O(n2) | O(n2) |
Приведенные временные показатели не позволяют рекомендовать алгоритм для использования его в практических целях. В обучении, ввиду своей относительной сложности, метод, несомненно, будет полезен.