Алгоритм сортировки Шелла (метод h-сортировки)

Некоторое усовершенствование сортировки простыми вставками предложено Д.Шеллом (Donald Lewis Shеll) в 1959 г.

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

Каждая h-сортировка программируется как сортировка простыми вставками. Затем h уменьшается и повторяется сортировка заново. Процесс заканчивается, когда h уменьшается до 1.

 

Рассмотрим последовательность 44, 55, 12, 42, 94, 18, 06, 67.

Сначала отдельно группируются и сортируются элементы, отстоящие друг от друга на расстоянии 4(четвертная сортировка):

44    55   12   42   94    18   06   67

Методом простой вставки сортируются массивы: 44-94, 55-18, 12-06, 42-67. После сортировки получаем массив:

44    18   06    42   94    55   12    67

 

2-сортировка дает следующие массивы для сортировки: 44-06-94-12, 18-42-55-67. После сортировки получаем массив:

06   18   12   42   44   55   94   67.

Уменьшаем h до 1 и сортируем весь массив, после чего получаем:

06   12   18   42   44   55   67   94.

 

Таким образом, программа разрабатывается как сортировка элементов массива для приращений h₁, h₂,…h_t с условиями h_t=1, h_i+1<h_i.

 

На первый взгляд можно сомневаться: если необходимо несколько проходов сортировки, причем в каждый включаются все элементы, то не добавят ли они больше работы, чем сэкономят?

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

 

Ясно, что такой метод дает упорядоченный массив, и каждый проход от предыдущих только выигрывает, так как каждая i-ая сортировка объединяет две группы уже отсортированные 2i-сортировкой (предыдущей).

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

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

Кнут рекомендовал последовательность 1, 4, 13, 40, 121,… (записанную в обратном порядке), где h_k-1=3h_k+1, h_t=1, t=[log₃ n]-1.

Он же рекомендовал последовательность 1, 3, 7, 15, 31,…, где h_k-1=2h_k+1, h_t=1, t=[log₂ n]-1.

 

Procedure Shellsort (var x: vector);

Var h, j, i, r: integer;

Begin

t:=round(ln(n)/ln(2))-1;

for m:=t downto 1 do

begin

h:=0;

For i:=1 to m do h:=2*h+1;

For i:=h+1 to N do

begin

r:=x[i]; j:=i-h;

while (j>=1) and (r<x[j]) do

begin

x[j+h]:=x[j];

dec(j,h);

end;

x[j+h]:=r

end;

end;

end (Shellsort);

 

 

Обменная сортировка с разделением (сортировка Хоара)

Сортировка методом простого обмена (методом "пузырька") является в среднем самой неэффективной. Это обусловлено самой идеей метода, который требует в процессе сортировки сравнивать и обменивать между собой только соседние элементы.

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

Алгоритм принадлежит Хоару (Charles Antony Richard Hoare), который опубликовал и тщательно проанализировал его в 1962 году.

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

 

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

Наша задача разделить массив на две части – левую, с элементами меньшими y и правую с элементами большими y. Будем просматривать массив с двух сторон. Двигаясь слева направо, найдем элемент x[i]>y, а, двигаясь справа налево, найдем элемент x[j]<y. Поменяем их местами и продолжим просмотр до тех пор, пока не встретимся в каком-то месте массива (j>j). Понятно, что после такого прохода массив будет разделен по принципу: слева стоят все элементы меньшие опорного, а справа – все элементы большие или равные.

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

 

Пример разделения 1 (по Кормену):

в качестве опорного элемента выбран y=x[1]=5:

5     3     2     6     4     1     3     7

3     3     2     6     4     1     5     7         

3     3     2     1     4     6     5     7

 

Пример разделения 2 (по Вирту):

в качестве опорного элемента выбран средний элемент y=42:

44   55   12   42   94   06   18   67

18   55   12   42   94   06   44   67

18   06   12   42   94   55   44   67

 

Пример разделения 3 (по Кнуту-Седгевику):

в качестве опорного элемента выбран первый элемент y=50, просмотр начинается со 2 элемента, затем происходит обмен j элемента с 1:

50   8     51   98   42   15   67   73

50   8     15   98   42   51   67   73

50   8     15   42   98   51   67   73

48   8     15   50   98   51   67   73

 

{Partition по Вирту}

       i:=1; j:=n;

        выбор опорного элемента y;

       repeat

                   while x[i]<y do i:=i + 1;

                   while x[j]>y do j:=j - 1;

                   if i<=j then begin z:=x[i]; x[i]:=x[j]; x[j]:=z

                              i:=i+1; j:=j-1 end;

       until i>j;

 

Заметим, что при сравнении while x[i]<y (while x[j]>y), ищется элемент не x[i]>y а x[i]>=y (соответственно справа не <, а <=), то есть y действует как барьерный элемент.

В рассмотренном примере 1 разделения массива, после завершения разделения значения индексов равны: i=6, j = 5. Заметим, что условие if i<=j then предшествующее обмену необходимо – без него мы ошибочно бы обменяли местами 4 и 6.

В рассмотренном примере 2 разделения массива, после завершения разделения значения индексов равны: i=5, j = 3.

Все элементы разделились по принципу:

x[k]<=y, k=1,…i-1;

x[k]>=y, k=j+1,n,

x[k]=y, k=j+1,…i-1.

 

Рассмотрим теперь разделение массива:

2     3     7     1     6     5     4

1     3     7     2     6     5     4

После завершения разделения значения индексов равны: i=2, j = 1. Здесь выбор среднего элемента в качестве опорного является неудачным, так как после деления имеем разбиение на левую часть из 1 элемента и правую часть из (n-1) элемента.

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

1     2     3     4     5     6     7

Здесь также длинная часть подмассива будет равна n-1, поэтому рекурсивный вызов потребуется n раз, что совершенно недопустимо, ввиду ограниченного размера стека. Как это не парадоксально, но алгоритм быстрой сортировки будет плохо работать в данном случае на упорядоченных массивах.

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

 

Хоар предложил два способа улучшить выбор опорного элемента y:

· выбирать случайным образом элемент массива,

· искать медиану трех случайно взятых элементов массива (средний по величине).

 

Ахо предлагает выбирать у как наибольшее значение из двух первых элементов массива.

Запишем теперь общий алгоритм, рекурсивно вызывая процедуру сортировки:

 

Procedure Quicksort(var x:vector);

Procedure sort(l,r: integer);

Var i, j: integer;

       y, z: integer;

Begin

i:=l; j:=r;

y:=x[(l+r) div 2];

       repeat

                   while x[i]<y do i:=i + 1;

                   while x[j]>y do j:=j - 1;

                   if i<=j then begin z:=x[i]; x[i]:=x[j]; x[j]:=z

                              i:=i+1; j:=j-1 end;

       until i>j;

if l < j then sort (l, j);

if i < r then sort(i, r)

end;

sort(1, n)

end; {quicksort}

 

Исключение рекурсии в этом алгоритме достигается использованием стека, в который запоминается запрос на сортировку одной из частей (для простоты - правой).

 

Procedure Quicksort(var x:vector);

Var i, j, l, r: integer;

       y, z: integer;

       S: stack;

Begin

Push(s,1,n);

Repeat

R:=pop(S);

L:=pop(S);

repeat

i:=l; j:=r;

y:=x[(l+r) div 2];

       repeat

                   while x[i]<y do i:=i + 1;

                   while x[j]>y do j:=j - 1;

                   if i<=j then

begin

z:=x[i]; x[i]:=x[j]; x[j]:=z

                                      i:=i+1; j:=j-1

end;

       until i>j;

if i < r then Push(S,i, r)

r:= j;

until l>=r;

until Empty(S);

end; {quicksort}

 

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

If j-l < r-i then

begin

if i < r then Push(S,i, r);

r:= j;

                   end

else

begin

if l < j then Push(S,l, j)

l:= i;

                   end;

 

Еще один способ улучшения метода, заключается в использовании простых методов для разделенных подмассивов малой длины N. Например, при N = 9, рекомендуется использовать сортировку простой вставкой.

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

Характеристики алгоритма «быстрой сортировки» зависят от удачного выбора элемента Y для разбиения.

В хорошем случае число сравнений C= N*log(N), M=(N/6)*log(N).

Таким образом, быстрая сортировка эффективна лишь в среднем - время работы пропорционально N*log(N), в худшем случае она может работать очень медленно, ее N2.

Быстрая сортировка не является устойчивой, в отличии, например, от простых вставок, слияния списков, простого выбора.

 

 

Сортировка методом слияний

Существует еще один метод сортировки элементов массива, эффективность которого сравнительно велика, - метод слияний.

Исторически метод слияния является одним из первых методов, предложенных для сортировки на ЭВМ еще в 1954 году, автором его является Джон фон Нейман.

 

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

Пусть массив а [1..n] разбивается на части длиной k, тогда первая часть - a[1], a[2],..., a[k], вторая- a[k+l], a[k+2],..., a[2k] и так далее. Если n не делится на k, то в последней части будет менее k элементов.

После того как массивы-части упорядочены, можно объединить их в упорядоченные массивы-части, состоящие не более чем из 2k элементов, которые далее объединить в упорядоченные массивы длиной не более 4k,и так далее, пока не получится один упорядоченный массив.

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

 

В более узком смысле слияние означает объединение двух или более упорядоченных массивов в один упорядоченный массив. Например, слияние двух массивов – 5 8 9 и 1 3 4 10 дает массив 1 3 4 5 8 9 10.

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

Рассмотрим этот метод на примере указанных двух массивов (5, 8, 9) и (1, 3, 4, 5, 8, 9, 10).

 

5     8     9

1     3     4     10

выбираем 1

 

5     8     9

3     4     10

выбираем 3

 

5     8     9

4     10

выбираем 4

 

5     8     9

10

выбираем 5

 

8     9

10

выбираем 8

9

10

выбираем 9

пустой массив

10

выбираем 10

 

Слияние намного более простая процедура, чем сортировка, так как общий объем работы по существу пропорционален количеству элементов m+n, но при этом используется дополнительный массив.

 

Алгоритм двухпутевого слияния реализован в следующей программе для отсортированных массивов x[1..m], y[1..n] с результирующим массивом z[1..n+m]. Небольшое упрощение введено добавлением в конец исходных файлов искусственных стражей x_m+1=y_n+1=¥.

 

Procedure Merge(x:vectorm;y:vectorn; var z: vectornm);

Var i,j,k: integer;

Begin

i:=1; j:=1;

x[m+1]:=Maxint; y[n+1]:=Maxint;

for k:=1 to n+m do

if x[i]<=y[j] then begin z[k]:=x[i]; inc(i) end

else begin z[k]:=y[j]; inc(j) end;

end;

 

 

Простое слияние

Алгоритм слияния, предложенный фон Нейманом, упорядочивает пары соседних чисел. Затем упорядоченные пары сливаются в упорядоченные четверки, восьмерки и т.д. Для хранения упорядоченных серий используется вспомогательный массив Y.

 

X    1     7      3     6      4     2      8     5

Y    1     7     3     6      2     4     5     8

X    1     3     6     7     2     4     5     8

Y    1     2     3     4     5     6     7     8

 

Этот алгоритм называется иногда вверх-направленным слиянием, учитывая направление сливаемых пар.

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

X    1      7     3     6     4     2     8     5

Y    1     5      2     3      6     4      8     7

X    1     5     7     8      6     4     3     2

Y    1     2     3     4     5     6     7     8

 

Чтобы не запутаться в двух виртуальных массивах, будем использовать один массив двойной длины array[1..2*n]. При этом сначала исходный массив находится в первой половине, в выходной – во второй, а затем наоборот.

Заведем булевскую переменную Up, которая определяет направление слияния: true – из первой половины во вторую, false – из второй половины в первую. Индексы i, j - отвечают за место, из которого берутся элементы для слияния, а k, l – за место куда пересылаются элементы. Переменная P определяет длину сливаемых серий (1, 2, 4, …).

Procedure merge(var x: vector);

Var up: boolean;

i, j, k, l: integer;

P: integer;

Begin

 Up:=true;

 p:=1;

 Repeat

if up then

Begin

 i:=1;j:=n; k:=n+1; l:=2*n;

end

 else

Begin

i:=n+1; j:=2*n; k:=1; l:=n

end;

{слияние p-серии из i, j в к, l}

  Up:=not up;

  P:=2*p

 Until p>=n;

End;

 

Слияние происходит следующим образом: сначала пересылка идет по адресу k, при этом индекс увеличивается на единицу, затем по адресу l, и индекс уменьшается на 1. Для упрощения будем считать, что пересылка всегда идет по адресу k с шагом h, но после каждого слияния будем чередовать h (либо +1, либо -1), а также менять местами значения k и l.

 

h:=1; m:=n;

Repeat

q:=p; r:=p; m:=m-2*p;

{слияние q элементов из i и r элементов из j}

h:=-h;

{обмен k, l};

Until m=0;

Сама процедура слияния должна предусмотреть копирование оставшегося остатка:

 

While (q<>0) and(r<>0) do

if x[i]<x[j]

 then begin x[k]:=x[i]; k:=k+h; i:=i+1; q:=q-1 end

Else begin x[k]:=x[j]; k:=k+h; j:=j-1; r:=r-1 end;

{копирование остатков из i или j}

 

Окончательный текст программы 

Procedure merge(var x: vector);

Var up: boolean;

I, j, k, l, t: integer;

P, h, q, r, m: integer;

Begin

 Up:=true;

 p:=1;

 Repeat

 m:=n; {общее число элементов во

   входных последовательностях,

   которые осталось слить}

 H:=1;

 if up

then

Begin

 i:=1;j:=n; k:=n+1; l:=2*n;

 end

else

Begin

i:=n+1; j:=2*n; k:=1; l:=n

end;

 Repeat

if m>= p then q:=p

      else q:=m; m:=m-q;

if m>= p then r:=p

      else r:=m; m:=m-r;

While (q<>0) and(r<>0) do

if x[i]<x[j]

then

begin

 x[k]:=x[i]; k:=k+h; i:=i+1; q:=q-1

end

else

begin

x[k]:=x[j]; k:=k+h;

 j:=j-1; r:=r-1

end;

 {копирование остатков}

 While r<>0 do

Begin

A[k]:=a[j]; k:=k+h;

 j:=j-1; r:=r-1

  End;

 While q<>0 do

Begin

A[k]:=a[i]; k:=k+h;

i:=i+1; q:=q-1

  End;

H:=-h; T:=k; k:=l; l:=t;

 Until m=0;

 Up:=not up;

 P:=2*p

 Until p>=n;

 if not up then

for i:=1 to n do x[i]:=x[i+n]

End;

Поскольку на каждом проходе p удваивается, то сортировка требует [log₂N] проходов. При каждом проходе перемещаются все N элементов. Поэтому характеристика M для сортировки слиянием оценивается как N*[log₂N].

Число сравнений C меньше, чем М, так как при копировании остатков сравнения не проводятся.