Сортировка Шелла

В 1959 году американский ученый Дональд Шелл опубликовал алгоритм сортировки, который впоследствии получил его имя – «Сортировка Шелла». Этот алгоритм может рассматриваться и как обобщение пузырьковой сортировки, так и сортировки вставками.

Идея метода заключается в сравнение разделенных на группы элементов последовательности, находящихся друг от друга на некотором расстоянии. Изначально это расстояние равно d или N/2, где N — общее число элементов. На первом шаге каждая группа включает в себя два элемента расположенных друг от друга на расстоянии N/2; они сравниваются между собой, и, в случае необходимости, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние d сокращается на d/2, и количество групп, соответственно, уменьшается. Постепенно расстояние между элементами уменьшается, и на d=1 проход по массиву происходит в последний раз.

Далее, на примере последовательности целых чисел, показан процесс сортировки массива методом Шелла. Для удобства и наглядности, элементы одной группы выделены одинаковым цветом.

Первое значение, соответствующее расстоянию d равно 10/2=5. На каждом шаге оно уменьшается вдвое. Элементы, входящие в одну группу, сравниваются и если значение какого-либо элемента, стоящего левее того с которым он сравнивается, оказывается больше (сортировка по возрастанию), тогда они меняются местами. Так, элементы путем внутригрупповых перестановок постепенно становятся на свои позиции, и на последнем шаге (d=1) сортировка сводится к проходу по одной группе, включающей в себя все N элементов массива. При этом число требуемых обменов оказывается совсем небольшим.

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

#include "stdafx.h"
#include <iostream>
using namespace std;
int i, j, n, d, count;
void Shell(int A[], int n) //сортировка Шелла
{
d=n;
d=d/2;
while (d>0)
{
for (i=0; i<n-d; i++)
{
j=i;
while (j>=0 && A[j]>A[j+d])
{
count=A[j];
A[j]=A[j+d];
A[j+d]=count;
j--;
}
}
d=d/2;
}
for (i=0; i<n; i++) cout<<A[i]<<" "; //вывод массива
}
//главная функция
void main()
{
setlocale(LC_ALL,"Rus");
cout<<"Размер массива > "; cin>>n;
int *A= new int[n]; //объявление динамического массива
for (i=0; i<n; i++) //ввод массива
{ cout<<i+1<<" элемент > "; cin>>A[i]; }
cout<<"\nРезультирующий массив: ";
Shell(A, n);
delete [] A; //освобождение памяти
system("pause>>void");
}

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

program ShellSorting;
uses crt;
type massiv=array[1..100] of integer;
var i, j, n, d, count: integer;
A: massiv;
procedure Shell(A: massiv; n: integer); {сортировка Шелла}
begin
d:=n;
d:=d div 2;
while (d>0) do
begin
for i:=1 to n-d do
begin
j:=i;
while ((j>0) and (A[j]>A[j+d])) do
begin
count:=A[j];
A[j]:=A[j+d];
A[j+d]:=count;
j:=j-1;
end;
end;
d:=d div 2;
end;
writeln;
for i:=1 to n do write(' ', A[i]); {вывод массива}
end;
{основной блок программы}
begin
write('Размер массива > '); read(n);
for i:=1 to n do {ввод массива}
begin write(i, ' элемент > '); readln(A[i]); end;
write('Результирующий массив: ');
Shell(A, n);
end.

Сортировка Шелла уступает в эффективности быстрой сортировки, но выигрывает у сортировки вставками. Сравнить скорость работы этих трех алгоритмов можно, воспользовавшись следующей таблицей.