ШЕЙКЕРНАЯ СОРТИРОВКА

Этот алгоритм, по сути, является модификацией сортировки обменом. Отличие состоит только в том, что если в сортировке обменом проходы осуществлялись только в одном направлении, то здесь направление каждый раз меняется. В шейкерной сортировке также можно проверять факт перестановки или запоминать место последней перестановки. В базовом алгоритме количество двойных проходов равно N div 2

ПРИМЕР: Шейкерная сортировка по возрастанию массива A из N целых чисел.

program Shaker;

var A:array[1..100] of integer;

N,i,k,x,j,d : integer;

begin

write('количество элементов массива ');

read(N);

for i:=1 to n do read(A[i]);

d:=1; i:=0;

for k:=n-1 downto 1 do { k - количество сравниваемых пар }

begin

i:=i+d;

for j:=1 to k do

begin

if (A[i]-A[i+d])*d>0 then

{меняем местами соседние элементы}

begin x:=A[i]; A[i]:=A[i+d]; A[i+d]:=x; end;

i:=i+d;

end;

d:=-d;

{меняем направление движения на противоположное}

end;

for i:=1 to n do write(A[i],' '); {упорядоченный массив}

end.