Эффективные методы сортировки

Сортировка вставками с уменьшающимся расстоянием (сортировка Шелла)

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

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

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

Приведём алгоритм для произвольной последовательности расстояний. Всего будет расстояний, удовлетворяющих условиям:.

procedure ShellSort;

const

T=5;

var

i,j,k,m: integer;

x: integer;

h: array [1..5] of integer;

begin

h[1]:=31; h[2]:=15; h[3]:=7; h[4]:=3; h[5]:=1;

for m:=1 to T do

begin

k:=h[m];

for i:=k+1 to N do

begin

x:=a[i];

j:=i-k;

while (j>k) and (x<a[j]) do

begin

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

j:=j-k;

end;

if (j>k) or (x>=a[j]) then

a[j+k]:=x

else

begin

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

a[j]:=x;

end;

end;

end;

end;

Анализ этого алгоритма – сложная математическая задача, у которой до сих пор нет полного решения. В настоящий момент неизвестно, какая последовательность расстояний даёт наилучший результат, но известно, что расстояния не должны быть кратными друг другу. Это необходимо, чтобы очередной проход не объединял две последовательности, до того никак не пересекавшиеся. На самом деле желательно, чтобы последовательности пересекались как можно чаще. Это связано со следующей теоремой: если последовательность после сортировке подвергается сортировке, то она при этом остаётся сортированной.

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

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

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

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

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

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

h0

h1

h3

h7

h8

h4

h9

h10

h2

h5

h11

h12

h6

h13

h14

h0

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

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

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

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

Метод, который мы рассмотрим, и был предложен Флойдом. Основа метода процедура sift (просеивание). Если у нас есть массив, то его элементы с номерами от до уже образуют пирамиду (т.к. в этих элементах нет таких пар, чтобы или). Эти элементы будут образовывать нижний ряд пирамиды. Заметим, что в нижнем ряду никакое упорядочивание не требуется. Затем начинается процесс расширения пирамиды. Причём за один шаг в неё будет включаться только один элемент, и этот элемент будет ставиться на своё место с помощью процедуры просеивания, которую мы сейчас рассмотрим.

procedure sift(L,R: integer);

var

i,j: integer;

x: integer;

begin

i:=L;

j:=2*i;

x:=a[i];

if (j<R) and (a[j]<a[j+1]) then

j:=j+1;

while (j<=R) and (x<a[j]) do

begin

a[i]:=a[j];

i:=j;

j:=2*j;

if (j<R) and (a[j]<a[j+1]) then

j:=j+1;

end;

a[i]:=x;

end;

Процесс получения пирамиды можно описать следующим образом:

L:=(N div 2)+1;

R:=N;

while L>1 do

begin

L:=L-1;

sift(L,R);

end;

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

while R>1 do

begin

x:=a[1];

a[1]:=a[R];

a[R]:=x;

R:=R-1;

sift(L,R);

end;

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

procedure HeapSort;

procedure sift(L,R: integer);

var

i,j: integer;

x: integer;

begin

i:=L;

j:=2*i;

x:=a[i];

if (j<R) and (a[j]<a[j+1]) then

j:=j+1;

while (j<=R) and (x<a[j]) do

begin

a[i]:=a[j];

i:=j;

j:=2*j;

if (j<R) and (a[j]<a[j+1]) then

j:=j+1;

end;

a[i]:=x;

end;

var

L,R: integer;

x: integer;

begin

L:=(N div 2)+1;

R:=N;

while L>1 do

begin

L:=L-1;

sift(L,R);

end;

while R>1 do

begin

x:=a[1];

a[1]:=a[R];

a[R]:=x;

R:=R-1;

sift(L,R);

end;

end;

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

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

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

Дата добавления: 2014-01-15