Сортування Шелла

Сортування Шелла

Демонстрація сортування Шелла з інтервалами 23, 10, 4, 1.
Клас	Алгоритм сортування
Структура даних	Масив
Найгірша швидкодія	$\Omega ( n log^2 n)$
Оптимальний	Переважно ні

Сортува́ння Ше́лла — це алгоритм сортування, що є узагальненням сортування включенням.

Алгоритм базується на двох тезах:

• Сортування включенням ефективне для майже впорядкованих масивів.
• Сортування включенням неефективне, тому що переміщує елемент тільки на одну позицію за раз.

Тому сортування Шелла виконує декілька впорядкувань включенням, кожен раз порівнюючи і переставляючи елементи, що розташовані на різній відстані один від одного.

Сортування Шелла не є стабільним.

Історія

Сортування Шелла названо начесть автора — Дональда Шелла, який опублікував цей алгоритм у 1959 році. В деяких пізніших друкованих виданнях алгоритм називають сортуванням Шелла-Мацнера, за ім'ям Нортона Мацнера. Але сам Мацнер стверджував: «Мені не довелось нічого робити з цим алгоритмом, і моє ім'я не має пов'язуватись з ним».

Ідея алгоритму

На початку обираються m-елементів: $d_1,d_2,\dots,d_m$, причому, $d_1 > d_2 > \dots > d_m = 1$.

Потім виконується m впорядкувань методом включення, спочатку для елементів, що стоять через $\;d_1$, потім для елементів через $\;d_2$ і т. д. до $\;d_m=1$.

Ефективність досягається тим, що кожне наступне впорядкування вимагає меншої кількості перестановок, оскільки деякі елементи вже стали на свої місця.

Псевдокод

Сам алгоритм не залежить від вибору m і d, тому будемо вважати, що вони задані.

$Shell\_Sort(A,N)\;$
1. for $k\leftarrow 1$ to $\;m$
2. do for $i\leftarrow d[k]+1$ to $\;N$
3.    do $a\leftarrow A[i]$
4.       $j\leftarrow i$
5.       while $\;j-d[k] \ge 1$ і $\;A[j-d[k]]>a$
6.       do $A[j]\leftarrow A[j-d[k]]$
7.          $j\leftarrow j-d[k]$
8.       $A[j]\leftarrow a$

Коректність алгоритма

Оскільки $\;d_m=1$ то на останньому кроці виконується звичайне впорядкування включенням всього масиву, а отже кінцевий масив буде впорядкованим.

Час роботи

Час роботи залежить від вибору значень елементів масиву d. Існує декілька підходів вибору цих значень:

• При виборі $d_1=\left\lfloor\frac{N}{2}\right\rfloor, d_2=\left\lfloor\frac{d_1}{2}\right\rfloor, d_3=\left\lfloor\frac{d_2}{2}\right\rfloor, \dots, d_m=1$ час роботи алгоритму, в найгіршому випадку, є $\;O(N^2)$.
• Якщо d — впорядкованний за спаданням набір чисел виду $\frac{3^j-1}{2}, j \in \mathbb N, d_i<N$, то час роботи є $\;O\left(N^\frac{3}{2}\right)$.
• Якщо d — впорядкованний за спаданням набір чисел виду $2^i3^j, i,j \in \mathbb N, d_k<N$, то час роботи є $\;O(N\log^2N)$.

Приклад роботи

Проілюструймо роботу алгоритму на вхідному масиві A = (5,16,1,32,44,3,16,7), d = (5,3,1).

1. Масив після впорядкування з кроком в 5: (3,16,1,32,44,5,16,7) — зроблено 1 обмін.
2. Масив після впорядкування з кроком 3: (3,7,1,16,16,5,32,44) — зроблено 3 обміна.
3. Масив після впорядкування з кроком 1: (1,3,5,7,16,16,32,44) — зроблено 5 обмінів.

Отже, весь масив впорядковано за 8 операцій обміну.

Реалізація (Паскаль/DELPHI)

program MyVerShellSort;
{$APPTYPE CONSOLE}
uses SysUtils;
type massive=array[1..100] of integer;
var A:massive; n:integer;
procedure RndArrInput(var a1:massive; n1:integer);
 var i1:integer;
begin
randomize;
for i1:=1 to n1 do
 a1[i1]:=10-random(20);
end;
procedure Arroutput(a2:massive; n2:integer);
var i2:integer;
begin
 for i2:=1 to n2 do
 write(a2[i2],' ');
end;
Procedure change (var k,l:integer);
 var tmp:integer;
 begin
  tmp:=k; k:=l; l:=tmp;
 end;
procedure ShellSort(var A:massive; n:integer);
Var i,j,h:integer;
Begin
 h:=N div 2;
 While h>0 do
 Begin
   For i:=1 to N-h do
   Begin
     j:=i;
     While (j>=1)and(A[j]>A[j+h]) do
     Begin
       change(a[j],a[j+h]);
       dec(j);
     End;
   End;
   h:=h div 2;
 end;
end;
begin
writeln('enter data:');
readln(n);
RndArrInput(a,n);
ArrOutPut(a,n); readln;
ShellSort(a,n);
ArrOutPut(a,n);
readln;
end.