Remkomplekty.ru

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

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

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

страницы: 1 2

Содержание

Улучшенные сортировки

В отличие от простых сортировок, имеющих сложность

N 2 , к улучшенным сортировкам относятся алгоритмы с общей сложностью

Необходимо, однако, отметить, что на небольших наборах сортируемых данных (N 1 базируется на уже известном нам алгоритме простых вставок ПрВст. Смысл её состоит в раздельной сортировке методом ПрВст нескольких частей, на которые разбивается исходный массив. Эти разбиения помогают сократить количество пересылок: для того, чтобы освободить «правильное» место для очередного элемента, приходится уже сдвигать меньшее количество элементов.

Алгоритм УлШелл

На каждом шаге (пусть переменная t хранит номер этого шага) нужно произвести следующие действия:

  1. вычленить все подпоследовательности, расстояние между элементами которых составляет kt;
  2. каждую из этих подпоследовательностей отсортировать методом ПрВст.

Нахождение убывающей последовательности расстояний kt, kt-1. k1 составляет главную проблему этого алгоритма. Многочисленные исследования позволили выявить её обязательные свойства:

  • k1 = 1;
  • для всех t kt > kt-1;
  • желательно также, чтобы все kt не были кратными друг другу (для того, чтобы не повторялась обработка ранее отсортированных элементов).

Дональд Кнут предлагает две «хорошие» последовательности расстояний:

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

Как же определить начальное значение для t (а вместе с ним, естественно, и для kt)?

Можно, конечно, шаг за шагом проверять, возможно ли вычленить из сортируемого массива подпоследовательность (хотя бы длины 2) с расстояниями 1, 3, 7, 15 и т. д. между её элементами. Однако такой способ довольно неэффективен. Мы поступим иначе, ведь у нас есть формула для вычисления kt = 2 t -1.

Итак, длина нашего массива (N) должна попадать в такие границы:

Прологарифмируем эти неравенства (по основанию 2):

Таким образом, стало ясно, что t можно вычислить по следующей формуле:

К сожалению, язык Pascal предоставляет возможность логарифмировать только по основанию е (натуральный логарифм). Поэтому нам придётся вспомнить знакомое из курса средней школы правило «превращения» логарифмов:

В нашем случае m = 2, z = e. Таким образом, для начального t получаем:

Однако при таком t часть подпоследовательностей будет иметь длину 2, а часть — и вовсе 1. Сортировать такие подпоследовательности незачем, поэтому стоит сразу же отступить ещё на 1 шаг:

Расстояние между элементами в любой подпоследовательности вычисляется так:

Количество подпоследовательностей будет равно в точности k. В самом деле, каждый из первых k элементов служит началом для очередной подпоследовательности. А дальше, начиная с (k + 1)–го, все элементы уже являются членами некоторой, ранее появившейся подпоследовательности, значит, никакая новая подпоследовательность не сможет начаться в середине массива.

Сколько же элементов будет входить в каждую подпоследовательность? Ответ таков: если длину всей сортируемой последовательности (N) можно разделить на шаг k без остатка, тогда все подпоследовательности будут иметь одинаковую длину, а именно:

Если же N не делится на шаг k нацело, то первые р подпоследовательностей будут длиннее на 1. Количество таких «удлинённых» подпоследовательностей совпадает с длиной «хвоста» — остатка от деления N на шаг k:

Реализация алгоритма УлШелл

Ради большей наглядности мы пожертвовали эффективностью и воспользовались алгоритмом ПрВст, а не ПрВстБар или БинВст. Дотошному же читателю предоставляется возможность самостоятельно улучшить предлагаемую реализацию:

program shell_sort ;
const
n = 18 ;
a : array [ 1 .. n] of Integer =
( 18 , 17 , 16 , 15 , 14 , 13 , 12 , 11 , 10 , 9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 ) ;
var ii , m , x , s , p , t , k , r , i , j : Integer ;
begin
t := Trunc ( Ln (n) / Ln ( 2 )) ;
repeat
t := t — 1 ;
k := ( 1 shl t) — 1 ;
p := n mod k ;
s := n div k ;
if p = 0 then
p := k
else
s := s + 1 ;

WriteLn (k , ‘-сортировка’ ) ;
for i := 1 to k do <берём и длинные, и короткие подпоследовательности>
begin
if i = p + 1 then
s := s — 1 ; <для коротких — уменьшаем длину>
for j := 1 to s — 1 do <метод ПрВст с шагом k>
if a[i + (j — 1 ) * k] > a[i + j * k] then
begin
x := a[i + j * k] ;
m := i + (j — 1 ) * k ;
while (m > 0 ) and (a[m] > x) do
begin
a[m + k] := a[m] ;
m := m — k ;
end ;
a[m + k] := x ;
end ;
for ii := 1 to n do
Write (a[ii] , ‘ ‘ ) ;
WriteLn ;
end ;
until k = 1 ;
end .

Результат работы

7–сортировки

3–сортировки

1–сортировка

Эффективность алгоритма УлШелл

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

N 3/2 . И хотя это несколько хуже, чем N*logN, всё–таки эта сортировка относится к улучшенным.

Пример сравнения сортировок: Вновь возьмём последовательность, для сортировки которой методом простых вставок ПрВст потребовалось 15 сдвигов (25 пересылок и 20 сравнений):

Теперь применим к ней метод Шелла.

Здесь N = 7, поэтому:

  1. 3–сортировки:

Состояние массива Сдвиги Сравнения Пересылки данных

0 шаг: 1323645
1 шаг: 1 323645 0 1 0
2 шаг: 13 23645 1 1+1 1+2
3 шаг: 123 3645 0 1 0
4 шаг: 1233 645 0 1 0
5 шаг: 12336 45 1 1+1 1+2
6 шаг: 123346 5 1 1+1 1+2
результат: 1233456 3 9 9

Читать еще:  Что значит в си шарп

При сортировке методом Шелла в сумме получилось 7 сдвигов (19 пересылок и 17 сравнений). Выигрыш по сравнению с методом простых вставок составляет 53% (24% экономится на пересылках и 15% — на сравнениях) 2 . Если вместо метода простых вставок ПрВст использовать метод бинарных вставок БинВст, то выигрыш по количеству сравнений будет ощутимее.

Кроме того, не нужно забывать, что в нашем примере последовательность очень коротка: N = 7. Для больших N (скажем, N = 10000) преимущество метода Шелла станет ещё заметнее.

Пирамидальная сортировка

Попытаемся теперь усовершенствовать другой рассмотренный выше простой алгоритм: сортировку простым выбором ПрВыб.

Р. Флойд предложил перестроить линейный массив в пирамиду — своеобразное бинарное дерево, — а затем искать минимум только среди тех элементов, которые находятся непосредственно «под» текущим вставляемым.

Просеивание

Для начала необходимо перестроить исходный массив так, чтобы он превратился в пирамиду, где каждый элемент «опирается» на два меньших. Этот процесс назвали просеиванием, потому что он очень напоминает процесс разделения некоторой смеси (камней, монет, т.п.) на фракции в соответствии с размерам частиц: на нескольких грохотах 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, то число наборов будет меньше.
Рассмотрим сортировку по шагам.

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

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

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

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

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

Рассмотрим следующий алгоритм сортировки массива 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 элементов.

Читать еще:  Вывод в консоль паскаль abc

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

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.

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

Разработан Дональдом Л. Шеллом в 1959 году.

Этот алгоритм классифицируется как сортировка вставками с убывающим шагом.

В первом проходе попарно переставляются элементы, находящиеся друг от друга на некотором растоянии, например, 9 позиций. Во втором проходе переставляются элементы, отстоящие на меньшее число позиций, например, 5. И т. д. На последнем шаге сортируются соседние элементы. На ранних этапах изучения алгоритма его исследователи отмечали: «Непонятно как алгоритм работает».
На самом деле принцип убывающих шагов может быть применён для различных базовых сортировок, в том числе для пузырьковой сортировки. В результате модификации получается сортировка расчёской.

Эффективность алгоритма заключается в том, что на каждом из промежуточных шагов сортируется либо небольшое число элементов, либо уже достаточно хорошо упорядоченные наборы элементов. Упорядоченность массива возрастает после каждого прохода.

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

Эффективность алгоритма проявляется даже в случае всего двух проходов с шагами h и 1. Время работы в этом случае зависит от размера массива как

.

А лучшее значение шага h оказывается равным

,

следствием этого является зависимость времени работы от размера массива, которую можно выразить как N 1,6667 или N 5/3 .

При большем числе проходов эффективность повышается. Тем не менее, в процессе изучения алгоритма был обнаружен порог эффективности, который долго не удавалось преодолеть (барьер N 1,5 ). Этот барьер можно преодолеть подбором шагов.

Изменение массива при сортировке по алгоритму Шелла будет имеет вид:

В ходе изучения алгоритма исследовалась зависимость среднего числа перестановок от размера массивов при 100 k +1, . 9, 5, 3, 1 => 1,09N 1,27

(3 k −1)/2, . 40, 13, 4, 1 => 1,66N 1,25

Общую формулу можно выразить как

или, упростив, как

Распространённой (хотя и далеко не самой эффективной) является последовательность шагов 9, 5, 3, 2, 1.

Кроме указанных формул используются числа Фибоначчи.

Рекомендуется избегать последовательности шагов в виде степеней двойки (. 16, 8, 4, 2, 1), так как это снижает эффективность алгоритма (хотя сортировка выполняется и в этом случае). Последний шаг обязательно должен быть единичным.

Один из рекомендуемых вариантов выбора последовательности шагов: принять шаги последнего и каждого предыдущего этапов h1 = 1, hs + 1 = 3hs + 1, и остановиться на некотором шаге ht , когда ht + 2N. В итоге получается последовательность шагов . 121, 40, 13, 4, 1 (такая же, как в случае (3 k −1)/2), которая является одной из самых эффективных. Возможны и другие, эвристически подбираемые последовательности шагов, ещё более эффективные (например, 120, 40, 12, 4, 1).
Возможен также расчёт шага первого этапа, исходя из размера массива, и уменьшение шага вдвое на каждом следующем этапе.

Сравнение зависимости времени работы для алгоритма Шелла и N-квадратичных алгоритмов.

Процедура сортировки методом Шелла на языке «Паскаль»

Аналогичная процедура на Си/Си++

Проверка условия j>=1 (для Паскаля или j>=0 для Си/Си++) предотвращает выход за пределы массива. Считается, что такие дополнительные проверки слегка снижают производительность алгоритма.

Ссылка на основную публикацию
Adblock
detector