Простой обмен

Любой метод сортировки так или иначе связан с обменом, т. е. с перестановкой двух элементов в памяти. Но если для других методов это действие является вспомогательным, то для обменной сортировки это основная характеристика процесса.

Идея сортировки простым обменом заключается в многократных попарных сравнениях рядом стоящих элементов таблицы и перестановке этих элементов в заданном порядке. Пусть нам задана таблица:

Номер элемента	1	2	3	4	5
Значение элемента	7	49	1	12	3

Будем просматривать ее от конца к началу (в принципе это не обязательно, можно организовать и обычный просмотр от начала к концу). Сравним 4-й и 5-й элементы. Они расположены не в порядке возрастания, поменяем их местами. Теперь значением 4-го элемента будет 3, а 5-го - 12. Сравним далее 3-й и 4-й элементы. Их оставим на месте. Сравнение 2-го и 3-го элементов показывает, что их нужно переставить. Теперь значение 2-го элемента - 1. И, наконец, сравним 1-й и 2-й элементы. Их тоже нужно поменять местами. Таким образом, получим:

Номер элемента	1	2	3	4	5
Значение элемента	1	7	49	3	12

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

Если вообразить себе, что элементы таблицы - это пузырьки в резервуаре с водой, каждый весом, равным своему значению (что и изображено на Рис. 2), то каждый проход с обменами по таблице приводит к "всплыванию пузырька" на соответствующий его весу уровень. Благодаря такой аналогии сортировка простым обменом получила название сортировки методом "пузырька". В примере на Рис. 2 первые два элемента последовательности уже упорядочены и "всплывает" третий элемент. Знак <= (а не <) показывает условие прекращения сравнений, именно этим достигается устойчивость сортировки "пузырьком".

Составим алгоритм решения данной задачи. Ясно, что основой алгоритма будет цикл, выполняющийся N-1 раз. Выбор границ (1 и N-1 или 2 и N) повлияет затем на задание индексов сравниваемых элементов, и только. Остановимся на второй паре границ.

I := 2 пока I <= N нц сравнить попарно элементы А_N, А_N-1, ..., А_I,А_I-1 1   I := I+1 кц

Разберем более детально пункт 1. Для попарного сравнения элементов нужен оператор цикла с границей, зависящей от I, так как при каждом новом проходе по таблице длина ее будет уменьшаться.

J := N пока J<=I нц сравнить a_j и a_j-i и при необходимости поменять их местами 1.1   J := J-1 кц

Пункт 1.1. уже легко записать в виде условного оператора:

1.1 если A[J-1]>A[J]   то X := A[J-l]; A[J-1] := A[J];A[J] := X все

Объединим теперь все шаги детализации в законченный алгоритм.

алг ОБМЕН(цел N, вещ таб A[1:N]) арг N, А рез А нач цел I, J, вещ Х I := 2 пока I<=N нц J := N   пока J>=I     нц если A[J-1]>A[J]     то X := A[J-1]       A[J-1] := A[J]       A[J] := X     все     J := J-1   кц   I := I+1 кц кон

В паскале

const m = 10;

type mass = array [l..m] of real;

procedure bubble(var a:mass; n:integer);

var i,j : integer; x : real;

begin for i := 2 to n do

for j := n downto 1 do

if a[j - 1] > a[j]

then begin

x := a[j - 1]; a[j - 1] := a[j];

a[j] := x

end

end;