Сортировка методом шелла паскаль

Сортировка методом Шелла.
Чтобы понять, как работает метод Шелла, необходимо разобраться в механизме работы метода вставки. Суть метода вставки состоит в следующем. Рассмотрим набор А[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 Окончательный отсортированный набор
Читайте также:  Kvi товары что это

Итак, ниже приведен текст программы. Я специально не удалял отладочные комментарии, осуществлявшие вывод промежуточных результатов. Вообще говоря, я писал программу сортировки по Шеллу лет 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;
item[j+gap]:=temp;

end;
end;
end;
begin
writeln;
randomize;
for i:=0 to n-1 do
begin
a[i]:=random(30)-10;
end;
assign(f,’shell_rs.txt’);
rewrite(f);
nit:=0;
PrintArrF(‘b ‘,0,a);

ResetTimePoint; < Отметить начало отсчета времени >
Shell(a,n);
GetTimePoint(h,m,s,hund);
writeln(‘ Сортировка заняла ‘,h,’ часов ‘,m,’ минут ‘,s,’.’,hund,’ секунд.’);
writeln;

PrintArrF(‘= ‘,0,a);
close(f);
end.
(******************************)

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 элементов массива. При этом число требуемых обменов оказывается совсем небольшим.

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

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

Adblock detector