5.2. Пузырьковая сортировка

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

Алгоритм 5.2. Пузырьковая сортировка

(см. скан)

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

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

В алгоритме 5.3 представлена «полная» пузырьковая сортировка. Это наиболее популярный и упрощенный вариант алгоритма 5.2. Ясно, что основным достоинством алгоритма полной пузырьковой сортировки является легкость программирования. Сложность же алгоритма 5.3 остается постоянной, равной и не зависит от расположения исходных данных.

Алгоритм 5.3. Полная пузырьковая сортировка

(см. скан)