Сортировка методом простого обмена может быть применена для любого массива. Этот метод заключается в последовательных просмотрах массива слева направо (от начала к концу) и обмене местами соседних элементов, расположенных “неправильно”, то есть таких, что 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.