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

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

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

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

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

На языке Паскаль оформим этот алгоритм в виде процедуры

Подпрограмма сортировки методом " пузырька" на языке Бейсик

Тот же алгоритм в виде подпрограммы на Фортране