На рисунке 4 приведен алгоритм шейкер - сортировки

0,3,5,7,8,16,20,27,29,31,32,36,37,42,47,67,77,85,86,91

0,3,86,20,27,67,31,16,37,42,8,47,7,84,5,29,91,36,77,32

End.

Repeat

Repeat

Repeat

Begin

Begin

Begin

Var

Очередным большим. Затем опять ищется больший элемент

Алгоритм сортировки простым выбором

4. Шейкер – сортировка.

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

Реализация на Паскале:

Program SortShaker;

FF:text;

Sort:array[1..20] of integer;

L,X,R,K,J:integer;

Sr,Re:integer;

procedure Change;

x:=sort[j-1];

sort[j-1]:=sort[j];

sort[j]:=x;

k:=j;

Inc(Re);

end;

Assign(FF,’text.txt’);

Rewrite(FF);

{Randomize; }

Sr:=0;

Re:=0;

for j:=1 to 20 do

Sort[j]:=random(100);

write(ff,sort[j],’,’);

end;

L:=2;

r:=20;

k:=20;

j:=r;

if sort[j-1] > sort[j] then Change;

inc(Sr);

j:=j-1;

until j< L;

L:=k+1;

j:=L;

if Sort[j-1] > Sort[j] then Change;

Inc(Sr);

j:=j+1;

until j>r;

r:=k-1;

until L>r;

Writeln;

for j:=1 to 20 do Write(FF,Sort[j],’,’);

writeln;

Writeln(FF,’Перестановок = ‘,Re:10,’ Сравнений = ‘,Sr:10);

Close(FF);

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

Перестановок = 73 Сравнений = 113

Рис. 4

Рассмотренными методами не исчерпывается перечень различных алгоритмов сортировки. Наиболее полное описание способов сортировки массивов вы найдете в пособии Д.Э. Кнута «Искусство программирования» т.3. Есть электронная версия книги, распространяемая на CD.

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