Сортировка методом Шелла.
Чтобы понять, как работает метод Шелла, необходимо разобраться в механизме работы метода вставки. Суть метода вставки состоит в следующем. Рассмотрим набор А[i], i=1,n.
Предположим, что первые k-1 элементов набора уже отсортированы. Тогда для k-того элемента необходимо найти такой индекс m (1 A[k-1] и k-тый элемент уже стоит на своем месте.) Если такое место найдено, то необходимо переместить туда k-тый элемент.
В реальности это означает, что все элементы с m-того до k-1-го должны быть перемещены на позицию вправа, а на место m-того элемента поместить k-тый. Рассмотрим следующий набор.
-5 -3 1 12 14 9 17
В нашем случае: n=7, k=6, m=4. Действительно, первые 5 элементов уже отсортированы, а шестой элемент (9) надо поместить на четвертую позицию между 1 и 12.
На деле алгоритм работает следующим образом. На k-том шаге имеем k-1 отсортированных элементов. Берем k-тый элемент и начинаем его менять с соседним слева j-тым элементом до тех пор, пока он будет меньше соседнего слева элемента. j=k-1,k-2. m
Как только мы совершим k-m перестановок, k-тый шаг закончен и мы имеем k отсортированных элементов.
Описанный алгоритм выполняется для k=2,n.
Теперь рассмотрим метод Шелла. Предлагается рассматривать не весь набор, а разбить его на части. Как? Возьмем некое число t и будем рассматривать только те элементы начального набора, индекс которых кратен t: i=t,2t,3t.
Очевидно, что начальный набор будет разбит на t наборов*. В самом деле, для t=3 и описанного выше набора имеем
1-й набор: i=3,6 (A: 1,9)
2-й набор: i=1,4,7 (A: -5,12,17)
3-й набор: i=2,5 (A: -3,14)
Для каждого из наборов произведем сортировку по методу вставки. А затем уменьшим число t и рассмотрим уже другое разбиение А на наборы. Для получения отсортированного исходного набора необходимо, чтобы последнее значение t было 1. Например, последовательность значений t может быть такова: 3,2,1. Для быстрой сходимости хорошо зарекомендовала себя последовательность 9,5,3,2,1.
Необходимо отметить, что разбиение на наборы – условное, мы не рассматриваем полученные наборы совершенно отдельно, просто при сортировке мы работаем с элементами исходного набора, отстоящими друг от друга на расстояние t. Может возникнуть вопрос, зачем такие сложности, если в итоге мы все равно пришли к методу вставки при t=1? Однако использование наборов позволяет минимизировать число перестановок элементов, поскольку при больших t мы перемещаем элементы на большие расстояния.
* Если 2t>n, то число наборов будет меньше.
Рассмотрим сортировку по шагам.
| N | t (gap) | Type | a[1] | a[2] | a[3] | a[4] | a[5] | a[6] | a[7] | Примечание |
| b | 16 | 2 | 12 | 14 | -5 | 12 | -2 | Начальный вывод | ||
| 1 | 5 | j | 16 | 2 | 12 | 14 | -5 | 16 | -2 | Первый элемент идет на место шестого. |
| 2 | 5 | i | 12 | 2 | 12 | 14 | -5 | 16 | -2 | . а шестой на место первого |
| 3 | 5 | j | 12 | 2 | 12 | 14 | -5 | 16 | 2 | Аналогично меняются местами второй и седьмой |
| 4 | 5 | i | 12 | -2 | 12 | 14 | -5 | 16 | 2 | |
| Уменьшаем t (gap) с 5 до 3 | ||||||||||
| 5 | 3 | i | 12 | -2 | 12 | 14 | -5 | 16 | 2 | Первый с четвертым менять не надо |
| 6 | 3 | j | 12 | -2 | 12 | 14 | -2 | 16 | 2 | Второй и пятый меняем местами |
| 7 | 3 | i | 12 | -5 | 12 | 14 | -2 | 16 | 2 | |
| 8 | 3 | i | 12 | -5 | 12 | 14 | -2 | 16 | 2 | Третий с шестым менять не надо |
| 9 | 3 | j | 12 | -5 | 12 | 14 | -2 | 16 | 14 | Четвертый на место седьмого. По идее седмой (это двойка) должен идти на место четвертого, но седьмой меньше первого, посему на место четвертого идет первый. . а седьмой отправляется на первое место. |
| 10 | 3 | j | 12 | -5 | 12 | 12 | -2 | 16 | 14 | |
| 11 | 3 | i | 2 | -5 | 12 | 12 | -2 | 16 | 14 | |
| Уменьшаем t (gap) с 3 до 2 | ||||||||||
| 12 | 2 | i | 2 | -5 | 12 | 12 | -2 | 16 | 14 | Первый с третьим и второй с четвертым менять не надо |
| 13 | 2 | i | 2 | -5 | 12 | 12 | -2 | 16 | 14 | |
| 14 | 2 | j | 2 | -5 | 12 | 12 | 12 | 16 | 14 | Третий идет на место пятого, первый на место третьго, а пятый идет на место первого. |
| 15 | 2 | j | 2 | -5 | 2 | 12 | 12 | 16 | 14 | |
| 16 | 2 | i | -2 | -5 | 2 | 12 | 12 | 16 | 14 | |
| 17 | 2 | i | -2 | -5 | 2 | 12 | 12 | 16 | 14 | Четвертый с шетсым и пятый с седьмым менять не надо. |
| 18 | 2 | i | -2 | -5 | 2 | 12 | 12 | 16 | 14 | |
| Уменьшаем t (gap) с 2 до 1 | ||||||||||
| 19 | 1 | j | -2 | -2 | 2 | 12 | 12 | 16 | 14 | Меняем первый со вторым |
| 20 | 1 | i | -5 | -2 | 2 | 12 | 12 | 16 | 14 | |
| 21 | 1 | i | -5 | -2 | 2 | 12 | 12 | 16 | 14 | |
| 22 | 1 | i | -5 | -2 | 2 | 12 | 12 | 16 | 14 | |
| 23 | 1 | i | -5 | -2 | 2 | 12 | 12 | 16 | 14 | |
| 24 | 1 | i | -5 | -2 | 2 | 12 | 12 | 16 | 14 | |
| 25 | 1 | j | -5 | -2 | 2 | 12 | 12 | 16 | 16 | Меняем шестой с седьмым |
| 26 | 1 | i | -5 | -2 | 2 | 12 | 12 | 14 | 16 | |
| 27 | = | -5 | -2 | 2 | 12 | 12 | 14 | 16 | Окончательный отсортированный набор | |
Итак, ниже приведен текст программы. Я специально не удалял отладочные комментарии, осуществлявшие вывод промежуточных результатов. Вообще говоря, я писал программу сортировки по Шеллу лет 15 назад, но следов ее у меня не осталось и мне поэтому пришлось писать сейчас ее заново. Полез в интернет посмотреть описание алгоритма, но они показались мне достаточно туманными, по крайней мере по тем описаниям написать программу не получилось. Чтобы разобраться взял готовый паскалевский текст (процедуру) и попробовал запустить. Не заработало. Текст этой неработающей процедуры приведен в самом низу. Тогда я взял текст процедуры на С и переписал это на Паскале. Это привело к успеху. И уже изучив промежуточные результаты я смог понять как это все работает. Я постарался изложить описание алгоритма доступно, чтобы было понятно, но, возможно, вам будет более понятно в другом изложении. Вариант на С был взят отсюда.
Чтобы сравнить время исполнения сортировки различными методами, включена процедура подсчета времени выполнения. Я сравнил сортировку по Шеллу с сортировкой методом вставки для n=7000. Шелл выполнился за 0.29 сек, а вставки – за 3.24 сек. Так что делайте выводы. Кстати, а что надо исправить в программе, чтобы из метода Шелла вышел метод вставки? 😉
| < сортировка Шелла > uses crt,timeunit; const n=7000; type DataItem=integer; DataArray=array[0..n-1] of DataItem; var a:DataArray; i,nit:word; f:text; h, m, s, hund : Word; Procedure PrintArr(a:DataArray); begin for i:=0 to n-1 do write(a[i]:4); end; Procedure PrintArrF(s:string;k:integer;a:DataArray); begin write(f,nit:4,’ h=’,k,’ ‘,s); nit:=nit+1; for i:=0 to n-1 do write(f,a[i]:4); writeln(f); end; procedure Shell(var item: DataArray; n:integer); const a:array[1..5] of byte = (9,5,3,2,1); var i,j,k,gap:integer; temp:DataItem; begin for k:=1 to 5 do begin gap:=a[k]; for i:=gap to n-1 do begin temp:=item[i]; j:=i-gap; while (temp =0) do begin item[j+gap]:=item[j]; j:=j-gap; end; end; ResetTimePoint; < Отметить начало отсчета времени > PrintArrF(‘= ‘,0,a); |
unit timeunit;
interface
Procedure ResetTimePoint; < Отметить начало отсчета времени >
Procedure GetTimePoint(var dh, dm, ds, dhund : Word);
< Выдать время от начала отсчета. См. процедуру SetTimePoint >
implementation
uses Dos;
type mytime=record
h, m, s, hund : Word; end;
var timebeg,timecurr:mytime;
Procedure ResetTimePoint; < Отметить начало отсчета времени >
begin
with timebeg do
GetTime(h,m,s,hund);
end;
Procedure GetTimePoint(var dh, dm, ds, dhund : Word);
Procedure DecHour(var t:mytime;dt:byte);
begin
if t.h>0 then dec(t.h);
end;
Procedure DecMin(var t:mytime;dt:byte);
begin
if t.m>dt-1 then dec(t.m,dt) else
begin
t.m:=60+t.m-dt;
DecHour(t,1);
end;
end;
Procedure DecSec(var t:mytime;dt:byte);
begin
if t.s>dt-1 then dec(t.s,dt) else
begin
t.s:=60+t.s-dt;
DecMin(t,1);
end;
end;
Procedure DecDSec(var t:mytime;dt:byte);
begin
if t.hund>dt-1 then dec(t.hund,dt) else
begin
t.hund:=60+t.hund-dt;
DecSec(t,1);
end;
end;
< Выдать время от начала отсчета. См. процедуру SetTimePoint >
begin
with timecurr do
begin
GetTime(h,m,s,hund);
if hund>=timebeg.hund then dhund:=hund-timebeg.hund
else begin dhund:=100+hund-timebeg.hund; DecSec(timecurr,1) end;
if s>=timebeg.s then ds:=s-timebeg.s
else begin ds:=60+s-timebeg.s; DecMin(timecurr,1) end;
if m>=timebeg.m then dm:=m-timebeg.m
else begin dm:=60+m-timebeg.m; DecHour(timecurr,1) end;
if h>=timebeg.h then dh:=h-timebeg.h
else dh:=24+h-timebeg.h;
end;
end;
begin
ResetTimePoint
end.
<Все. Дальше пошли справочные материалы. Сначала текст на С, а потом неработающий на Паскале >
(*
void shall_sort(int *array, int n)
<
int i, j, k, gap, temp;
int a[] = <9, 5, 3, 2, 1>;
for (k = 0; k = 0; j-=gap)
array[j+gap] = array[j];
array[j+gap] = temp;
>
>
>
*)
procedure Shell1(var item: DataArray; count:integer);
< doesn’t work >
const t = 5;
var i, j, k, s, m: integer;
h: array[1..t] of integer;
x: DataItem;
begin
h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=2; h[5]:=1;
for m := 1 to t do
begin
k:=h[m];
s:=-k;
for i := k+1 to count do
begin
x := item[i];
j := i-k;
if s=0 then
begin
s := -k;
s := s+1;
item[s] := x;
end;
while (x
В 1959 году американский ученый Дональд Шелл опубликовал алгоритм сортировки, который впоследствии получил его имя – «Сортировка Шелла». Этот алгоритм может рассматриваться и как обобщение пузырьковой сортировки, так и сортировки вставками.
Идея метода заключается в сравнение разделенных на группы элементов последовательности, находящихся друг от друга на некотором расстоянии. Изначально это расстояние равно d или N/2, где N — общее число элементов. На первом шаге каждая группа включает в себя два элемента расположенных друг от друга на расстоянии N/2; они сравниваются между собой, и, в случае необходимости, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние d сокращается на d/2, и количество групп, соответственно, уменьшается. Постепенно расстояние между элементами уменьшается, и на d=1 проход по массиву происходит в последний раз.
| Худшее время |
|---|
зависит от выбранных шагов
О(n) всего, O(1) дополнительно
Пример
Пусть дан список 
и выполняется его сортировка методом Шелла, а в качестве значений 
выбраны 
.
На первом шаге сортируются подсписки 
, составленные из всех элементов , различающихся на 5 позиций, то есть подсписки 
, 
, 
, 
, 
.
В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов.
Процесс завершается обычной сортировкой вставками получившегося списка.
Реализация алгоритма на различных языках программирования:
В 1959 году американский ученый Дональд Шелл опубликовал алгоритм сортировки, который впоследствии получил его имя – «Сортировка Шелла». Этот алгоритм может рассматриваться и как обобщение пузырьковой сортировки, так и сортировки вставками.
Идея метода заключается в сравнение разделенных на группы элементов последовательности, находящихся друг от друга на некотором расстоянии. Изначально это расстояние равно d или N/2, где N — общее число элементов. На первом шаге каждая группа включает в себя два элемента расположенных друг от друга на расстоянии N/2; они сравниваются между собой, и, в случае необходимости, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние d сокращается на d/2, и количество групп, соответственно, уменьшается. Постепенно расстояние между элементами уменьшается, и на d=1 проход по массиву происходит в последний раз.
Далее, на примере последовательности целых чисел, показан процесс сортировки массива методом Шелла. Для удобства и наглядности, элементы одной группы выделены одинаковым цветом.
Первое значение, соответствующее расстоянию d равно 10/2=5. На каждом шаге оно уменьшается вдвое. Элементы, входящие в одну группу, сравниваются и если значение какого-либо элемента, стоящего левее того с которым он сравнивается, оказывается больше (сортировка по возрастанию), тогда они меняются местами. Так, элементы путем внутригрупповых перестановок постепенно становятся на свои позиции, и на последнем шаге (d=1) сортировка сводится к проходу по одной группе, включающей в себя все N элементов массива. При этом число требуемых обменов оказывается совсем небольшим.