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

В 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.

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

Сортировка вставками

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

Быстрая сортировка

Худший случай

O(n2)

O(n2)

O(n2)

Лучший случай

O(n)

O(n log n)

O(n log n)

Средний случай

O(n2)

Зависит от расстояния между элементами

O(n log n)

Рейтинг
( 1 оценка, среднее 5 из 5 )
Загрузка ...