Foreversoft.ru

IT Справочник
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Метод шелла паскаль

Метод шелла паскаль

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

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

зависит от выбранных шагов

О(n) всего, O(1) дополнительно

Пример

Пусть дан список и выполняется его сортировка методом Шелла, а в качестве значений выбраны .

На первом шаге сортируются подсписки , составленные из всех элементов , различающихся на 5 позиций, то есть подсписки , , , , .

В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов.

Процесс завершается обычной сортировкой вставками получившегося списка.

Реализация алгоритма на различных языках программирования:

Метод шелла паскаль

Сортировка Шелла является довольно интересной модификацией алгоритма сортировки простыми вставками.

Рассмотрим следующий алгоритм сортировки массива a[0].. a[15].

1. Вначале сортируем простыми вставками каждые 8 групп из 2-х элементов (a[0], a[8[), (a[1], a[9]), . , (a[7], a[15]).

2. Потом сортируем каждую из четырех групп по 4 элемента (a[0], a[4], a[8], a[12]), . (a[3], a[7], a[11], a[15]).

В нулевой группе будут элементы 4, 12, 13, 18, в первой — 3, 5, 8, 9 и т.п.

3. Далее сортируем 2 группы по 8 элементов, начиная с (a[0], a[2], a[4], a[6], a[8], a[10], a[12], a[14]).

4. В конце сортируем вставками все 16 элементов.

Очевидно, лишь последняя сортировка необходима, чтобы расположить все элементы по своим местам. Так зачем нужны остальные ?

Hа самом деле они продвигают элементы максимально близко к соответствующим позициям, так что в последней стадии число перемещений будет весьма невелико. Последовательность и так почти отсортирована. Ускорение подтверждено многочисленными исследованиями и на практике оказывается довольно существенным.

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

Использованный в примере набор . 8, 4, 2, 1 — неплохой выбор, особенно, когда количество элементов — степень двойки. Однако гораздо лучший вариант предложил Р.Седжвик. Его последовательность имеет вид

При использовании таких приращений среднее количество операций: O(n 7/6 ), в худшем случае — порядка O(n 4/3 ).

Обратим внимание на то, что последовательность вычисляется в порядке, противоположном используемому: inc[0] = 1, inc[1] = 5, . Формула дает сначала меньшие числа, затем все большие и большие, в то время как расстояние между сортируемыми элементами, наоборот, должно уменьшаться. Поэтому массив приращений inc вычисляется перед запуском собственно сортировки до максимального расстояния между элементами, которое будет первым шагом в сортировке Шелла. Потом его значения используются в обратном порядке.
При использовании формулы Седжвика следует остановиться на значении inc[s-1], если 3*inc[s] > size.

Часто вместо вычисления последовательности во время каждого запуска процедуры, ее значения рассчитывают заранее и записывают в таблицу, которой пользуются, выбирая начальное приращение по тому же правилу: начинаем с inc[s-1], если 3*inc[s] > size.

Глупая сортировка и некоторые другие, поумнее


В прошлой статье мы оттолкнулись от так называемой глупой сортировки и путём нехитрых метаморфоз получили всем известную пузырьковую сортировку. Трансформируя последнюю пришли к целому вороху обменных способов упорядочивания массивов. Один из которых, между прочим, на структурах до нескольких тысяч элементов, даже работает быстрее чем быстрая сортировка.

Сегодня мы снова возьмём за основу stupid sort и внесём в неё другое маленькое, но существенное изменение. В результате получим совершенного другой эволюционный ряд сортировочных алгоритмов.

Глупая сортировка

Кому лень смотреть первую серию, напомню, что из себя представляет глупая сортировка. Обходим по порядку массив и, встретив два неотсортированных соседа, меняем их местами. Затем возвращаемся на старт и «наша песня хороша, начинай сначала». Если в этой сортировке вместо возвращения просто идти дальше, то в получаем «пузырёк», который, как оказалось, тоже можно совершенствовать до бесконечности O(n log n).

Теперь поступим иначе. Обменяв два элемента, мы изменили порядок в массиве, и нужно как-то выяснить не вступает ли новое расположение в диссонанс с теми элементами, которые мы проверили ранее. Не будем прыгать в начало массива, не станем идти вперёд, а сделаем шаг назад. Если там теперь тоже не отсортировано, то установим строгую очерёдность по старшинству и сделаем ещё шаг назад. И так будем отступать до тех пор, пока не достигнем отсортированной части массива. После этого снова можно двигаться дальше.

Ну что ж, поздравляю тех, кто не знал про этот способ. Вы только что с познакомились с методом, имя которому…

Гномья сортировка

image: голландский садовый гном

Хотя гномам этот способ известен уже много столетий, человеческая раса о нём узнала совсем недавно. Уже 55 лет как человечество использовало сортировку слиянием, прошло 40 лет как стала известна быстрая сортировка, уже спустя 35 лет как разработана пирамидальная сортировка – и вот, только в 2000 году, этот бесхитростный, практически детский приём, был исследован Диком Груном:

Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.

Разумеется, люди предложили способ по улучшению, до которого не додумались консервативные лилипуты. Если запоминать место в котором встретилось неотсортированное недоразумение и сделать несколько корректирующих итераций назад, то после наведения порядка в тылах, можно прыгнуть сразу туда где прервались и следовать по массиву далее.

Так немного быстрее, хотя принципиально это временную сложность не улучшает, она как была так и остаётся O(n 2 ). Но зато это приводит нас не только к новому способу сортировки, а даже к целому новому классу сортировок. И имя этой группе алгоритмов – «Сортировки вставками».

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

Здесь поступательно обрабатываются отрезки массива, начиная с первого элемента и затем расширяя подмассив, вставляем на своё место очередной неотсортированный элемент.

Для вставки используется буферная область памяти, в которой хранится элемент, ещё не оказавшийся на своём место (так называемый ключевой элемент). В подмассиве, начиная с правого края, просматриваются элементы и сравниваются с ключевым. Если больше ключевого, то очередной элемент сдвигается на одну позицию вправо, освобождая место для последующих элементов. Если в результате этого перебора попадается элемент, меньший или равный ключевому, то значит в текущую свободную ячейку можно вставить ключевой элемент.

Тот же оптимизированный «гномик», но только для обмена используется буфер.

Временная сложность у этой сортировки O(n 2 ), но не это главное. Сортировка вставками, судя по всему — наиболее эффективный вариант для почти отсортированных массивов. Этот факт используется в некоторых сложных алгоритмах сортировки. Помнится, я уже когда-то рассказывал про FlashSort, там при помощи вероятностного распределения быстро создаётся почти отсортированный массив, который затем доупорядочивается сортировкой вставками. Сортировка вставками используется в финальной части JSort, где путём построения неполной кучи массив оперативно почти сортируется. Timsort начинает сортировку массива с нахождения в нём почти упорядоченных отрезков, они также сортируются вставочным методом, а затем объединяются модифицированной сортировкой слиянием.

Как изволите видеть, хотя сортировка вставками сама по себе работает медленно, её сфера применения очень широка.

Ну, раз столь много букв написано про insertion sort, то рассказ будет не полным, если не сказать пару добрых слов про алгоритм, который называется…

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

Про сортировку Шелла уже есть статья на Хабре, поэтому буду очень краток.

Позавчера уже писал как из очень медленного «пузырька» можно сделать очень быструю «расчёску». Для этого сначала нужно сравнивать не соседей, а элементы, между которыми достаточно внушительное расстояние. Это позволяет на начальном этапе маленькие значения закинуть поближе к началу массива, большие – поближе к концу. Затем уменьшая разрыв, уже наводить в массиве локальные порядки.

Shell sort использует ту же стратегию. Сортируем вставкой подгруппы элементов, но только в подгруппе они идут не в ряд, а равномерно выбираются с некоторой дельтой по индексу. Методично уменьшая расстояние между элементами этих несвязных подмножеств, мы сортируем уже намного быстрее.

Временная сложность у «шелла» – достаточно сложный вопрос. Дело в том, что до сих пор нет строгой формулы, по которой строится оптимальный числовой ряд изменяющихся расстояний между элементами в подгруппах. Последовательность строится эмпирически, на основании многочисленных тестов с различными входными данными и последнее наилучшее уточнение для вышеупомянутых «дельт» было определено в 2001 году:

1, 4, 10, 23, 57, 132, 301, 701.

Сортировку Шелла придумал, как ни странно, Дональд Шелл в 1959 году. В 2014-м автору, кстати, исполняется 90 лет, живёт и здравствует до сих пор, недавно в третий раз женился. Так что, изобретайте алгоритмы, держите мозги в тонусе – и переживёте 3-х жён полноценная многолетняя творческая деятельность Вам обеспечена.

Turbo Pascal Examples

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

Худшее время
Лучшее время
Среднее время
Затраты памяти
Nt (gap)Typea[1]a[2]a[3]a[4]a[5]a[6]a[7]Примечание
b1621214-512-2Начальный вывод
15j1621214-516-2Первый элемент идет на место шестого.
25i1221214-516-2. а шестой на место первого
35j1221214-5162Аналогично меняются местами второй и седьмой
45i12-21214-5162
Уменьшаем t (gap) с 5 до 3
53i12-21214-5162Первый с четвертым менять не надо
63j12-21214-2162Второй и пятый меняем местами
73i12-51214-2162
83i12-51214-2162Третий с шестым менять не надо
93j12-51214-21614Четвертый на место седьмого. По идее седмой (это двойка) должен идти на место четвертого, но седьмой меньше первого, посему на место четвертого идет первый. . а седьмой отправляется на первое место.
103j12-51212-21614
113i2-51212-21614
Уменьшаем t (gap) с 3 до 2
122i2-51212-21614Первый с третьим и второй с четвертым менять не надо
132i2-51212-21614
142j2-51212121614Третий идет на место пятого, первый на место третьго, а пятый идет на место первого.
152j2-5212121614
162i-2-5212121614
172i-2-5212121614Четвертый с шетсым и пятый с седьмым менять не надо.
182i-2-5212121614
Уменьшаем t (gap) с 2 до 1
191j-2-2212121614Меняем первый со вторым
201i-5-2212121614
211i-5-2212121614
221i-5-2212121614
231i-5-2212121614
241i-5-2212121614
251j-5-2212121616Меняем шестой с седьмым
261i-5-2212121416
27=-5-2212121416Окончательный отсортированный набор

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

Читать еще:  Файл журнала ошибок
Ссылка на основную публикацию
Adblock
detector