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

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

Например, задана таблица

Необходимо организовать ее просмотр от конца к началу или от начала к концу. Сравнить значения элементов 4 и 5 и поменять их местами, так как они расположены не по возрастанию. Далее сравнить элементы 3 и 4. Они остаются на своих местах, и т. д.

В результате минимальный элемент переместится в таблице на первое место и новая таблица после первого «прохода» примет вид:

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

1. i=2
2. Сравнить попарно элементы А _n , А _n-1 , ..., А _i , A _i-1 .
3. i = i + 1
4. Если i ≤ N, то повторить с п. b.

Для попарного сравнения элементов можно использовать для схемы алгоритмов графический цикл с параметром (символ «Подготовка»), зависящий от i, так как при каждом новом проходе по таблице длина ее будет уменьшаться.

Рассмотрим «попарное сравнение» более подробно.

1. j=N
2. Сравнить А _j и А _j-1 и при необходимости поменять местами
3. j=j-1
4. Если j > i, то повторить с п. b.

Сравнение в п. b можно записать, используя операцию переприсвоения:
Если A _j > A _j-1 , To X = A _j-1 ; A _j-1 = A _j ;A _j = x.
На рис. 1.16 представлена схема алгоритма пузырьковой сортировки, для которой использован цикл с постусловием.