Шейкерная сортировка

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

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

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

Procedure Shaker_Sort(n:word;Var a:t);

Var

j,k,l,r:word;

x:integer;

Begin

l:=2; r:=n; k:=n;

Repeat

For j:=r DownTo l Do

If a[j-1]>a[j] Then

begin

x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; k:=j;

end;

l:=k+1;

For j:=l To r Do

If a[j-1]>a[j] Then

begin

x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; k:=j;

end;

r:=k-1;

Until l>r

End;{Shaker_Sort}

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

Пирамида определяется как последовательность ключей h_l, h_l+1,..., h_r такая, что h_i<=h_2i, h_i<=h_2i+1 для всякого i=l,...,r/2.

Предположим, что дана пирамида с элементами h_l+1,..., h_r для некоторых значений l и r и нужно добавить новый элемент x для того, чтобы сформировать расширенную пирамиду h_l,..., h_r. Новый элемент x сначала помещается в вершину дерева, а затем “просеивается” по пути, на котором находятся меньшие по сравнению с ним элементы, которые одновременно поднимаются вверх; таким образом, формируется новая пирамида.

Здесь в процедуре Heap_Sort вызывается процедура Sift, которая реализует алгоритм формирования пирамиды.

Procedure Heap_Sort(n:word;Var a:t);

Var

l,r:word;x:integer;

Procedure Sift;

Label 13;

Var i,j:word;

Begin

i:=l; j:=2*i; x:=a[i];

While j<=r Do

begin

If j<r Then

If a[j]<a[j+1] Then j:=j+1;

If x>=a[j] Then Goto 13;

a[i]:=a[j]; i:=j; j:=2*i;

end;

13: a[i]:=x

End;{Sift}

BEGIN

l:=(n div 2)+1; r:=n;

While l>1 Do

begin

l:=l-1; Sift

end;

While r>1 Do

begin

x:=a[1]; a[1]:=a[r]; a[r]:=x;

r:=r-1; Sift

end

END;{Heap_Sort}