07.04.2017 / by / Гуманитарный Рунет / No Comments

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

В 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

{

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

}

void main() //главная функция

{

cout<<"Размер массива > «; cin>>n;

int *A= new int[n]; //объявление динамического массива

for (i=0; i

{

cout< «;

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(n2) O(n2)
Лучший случай O(n) O(n log n) O(n log n)
Средний случай O(n2) Зависит от расстояния между элементами O(n log n)


Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *