Обменная сортировка

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

Просмор пар может начинаться с начала массива или с его конца, в последнем случае алгоритм называют алгоритмом пузырьковой сортировки. Подробнее об этом можно ознакомиться в [2,3].

Рассмотрим работу алгоритма по схеме.

Схема алгоритма обменной сортировки

нет

да

нет да

Key - ключ, определяющий была ли перестановка пар элементов;

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

Текст программы обменной сортировки

Uses crt;

Var M:array[1..1000] of integer;

i,Z,n:integer; Key:byte;

Begin Clrscr;

{Ввод n и формирование массива М как в предыдущей программе}

Repeat

Key:=0;

For i:=1 to n-1 do

If M[i] > M[i+1] then

begin

Z:=M[i];

M[i]:=M[i+1];

M[i+1]:=Z;

Key:=1;

end;

Until Key=0;

Writeln(' Упорядоченный массив');

For i:=1 to n do write(M[i],' '); readkey;

End.