Сортировка методом простого обмена

Сортировка методом простого обмена может быть применена для любого массива. Этот метод заключается в последовательных просмотрах массива слева направо (от начала к концу) и обмене местами соседних элементов, расположенных “неправильно”, то есть таких, что i < j, а a[i] > a[j]. Опишем этот метод подробнее.

Начнем просмотр с первой пары элементов (a[1] и a[2]), если первый элемент этой пары больше второго, то меняем их местами, иначе оставляем без изменения. Затем берем вторую пару элементов (a[2] и a[3]), если a[2] > a[3], то меняем их местами и так далее. На первом шаге будут просмотрены все пары элементов массива a[i] и a[i+1] для i от 1 до n-1. В результате максимальный элемент массива переместится в конец массива.

Поскольку самый большой элемент находится на своем месте, рассмотрим часть массива без него, то есть с первого до (n-1) - го элемента. Повторим

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

Пример

Отсортируем по возрастанию методом простого обмена массив из 5 элементов: 5 4 8 2 9

Длина текущей части массива - n-k+1, где k - номер просмотра, i - номер проверяемой пары; номер последней пары - n-k. За вертикальной чертой располагаются отсортированные элементы.

Первый просмотр: рассматривается весь массив.

i = 1 5 >4 8 2 9

обмен

i = 2 4 5 < 8 2 9

нет обмена

i = 3 4 5 8 > 2 9

обмен

i = 4 4 5 2 8 < 9

нет обмена

9 стоит на своем месте.

Второй просмотр: рассматриваем часть массива с первого до четвертого элемента.

i = 1 4 < 5 2 8 ½ 9

нет обмена

i = 2 4 5 > 2 8 ½ 9

обмен

i = 3 4 2 5 < 8 ½ 9

нет обмена

8 стоит на своем месте.

Третий просмотр: рассматриваемая часть массива содержит три первых элемента.

i = 1 4 > 2 5 ½ 8 9

обмен

i = 2 2 4 < 5 ½ 8 9

нет обмена

5 стоит на своем месте.

Четвертый просмотр: рассматриваем последнюю пару.

i = 1 2 4 < 5 ½ 8 9

нет обмена

4 стоит на своем месте.

Для самого маленького элемента (2) остается только одно место - первое.

Итак, наш массив отсортирован по возрастанию элементов методом простого обмена. Этот метод называют также методом “пузырька”. Название это происходит от обратной интерпретации, при которой в процессе выполнения сортировки более “ легкие ” элементы (элементы с заданным свойством) мало - помалу всплывают на “поверхность”.

Программа “пузырьковой” сортировки.

program n2;const n=5;type ar=array [1..n] of integer;

var i:integer;

a:ar;

procedure sorting2(var a:ar);

var k,i,t:integer;

{k - номер просмотра (изменяется от 1 до n-1)

i - номер рассматриваемой пары

t - промежуточная переменная для перестановки местами элементов}

begin

for k:=1 to n-1 do

{цикл по номеру просмотра}

for i:=1 to n-k do

if a[i]>a[i+1] then

{перестановка элементов}

begin

t:=a[i];

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

a[i+1]:=t;

end;

end;

begin

writeln('Введите исходный массив:');

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

sorting2(a);

writeln('Отсортированный массив:');

for i:=1 to n do write(a[i],' ');

writeln;

end.

Дата добавления: 2014-11-09