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

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

Принцип метода:

Начиная от конца массива и до его начала поочередно сравниваются два соседних элемента, и если их взаиморасположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и так далее до начала массива.

После одного такого прохода на последней 0-ой позиции массива будет стоять минимальный элемент («всплыл» первый «пузырек»). Поскольку минимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до 1-го элемента. И так далее. Всего требуется n-1 проход.

Пример 1. Расположим массив сверху вниз, от нулевого элемента - к последнему.

Шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.

После нулевого прохода по массиву «вверху» оказывается самый «легкий» элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом, второй по величине элемент поднимается на правильную позицию и т.д.

Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию.