Сортировка методом прямого обмена (пузырьковая)

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

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

Такой метод широко известен под именем "пузырьковая сортировка".

Алгоритм:

for i = 2 to n

for j = n to i step -1

if a(j) < a(j - 1 ) then

x = a(j - 1 )

a(j - 1 ) = a(j)

a(j) = x

endif

next j

next i

return

В нашем случае получился один проход “вхолостую”. Чтобы лишний раз не просматривать элементы, а значит проводить сравнения, затрачивая на это время, можно ввести флажок fl, который остается в значении false, если при очередном проходе не будет произведено ни одного обмена.

fl = true

for i = 2 to n

if fl = false then return

endif

fl = false

for j = n to i step -1

if a(j) < a(j - 1 ) then

fl = true

x = a(j - 1 )

a(j - 1 ) = a(j)

a(j) = x

endif

next j

next i

return

Улучшением пузырькового метода является шейкерная сортировка, где после каждого прохода меняют направление во внутреннем цикле.