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

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

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

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

Рисунок 6.4 – Пример сортировки Шелла

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

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

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() //главная функция

{

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; //освобождение памяти

}

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

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.

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

	Сортировка вставками	Сортировка Шелла	Быстрая сортировка
Худший случай	O (n2)	O (n 2)	O (n 2)
Лучший случай	O (n)	O (n log n)	O (n log n)
Средний случай	O (n 2)	Зависит от расстояния между элементами	O (n log n)