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

Лекция

Привет, сегодня поговорим про шейкерная перемешиванием сортировка, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое шейкерная перемешиванием сортировка , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

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.

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

Лучший случай	Средний случай	Наихудший случай
O(n)	O(n²)	O(n²)

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

На этом все! Теперь вы знаете все про шейкерная перемешиванием сортировка, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое шейкерная перемешиванием сортировка и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов

Из статьи мы узнали кратко, но содержательно про шейкерная перемешиванием сортировка

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

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

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

Комментарии

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

Алгоритмы и теория алгоритмов

Термины: Алгоритмы и теория алгоритмов