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

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

Рисунок 1 показывает первый проход пузырьковой сортировки. Затенёные элементы будут сравниваться для определения в правильном ли порядке они стоят. Если в списке \(n\) элементов, то за первый проход потребуется сравнить \(n-1\) пару. Важно отметить, что поскольку наибольшее значение - часть пары, то оно будет перемещаться вдоль списка до завершения прохода.

Рисунок 1: bubbleSort: первый проход

К началу второго прохода наибольшее значение стоит на своём месте. Остаётся \(n-1\) число для сортировки, или \(n-2\) пары. Поскольку каждый проход помещает следующее наибольшее значение на положенное место, то общее количество проходов равняется \(n-1\). После завершения \(n-1\) прохода наименьший элемент будет на верной позиции без дополнительных вычислений. ActiveCode 1 демонстрирует функцию bubbleSort целиком. Она принимает список в качестве параметра и при необходимости изменяет его с помощью перестановок элементов.

Операция перестановки, иногда называемая “обменом”, в Python несколько проще, чем в большинстве других языков программирования. Обычно перестановка местами двух элементов списка требует временного сохранения их местоположения (дополнительный объём памяти). Следующий фрагмент кода

temp = alist[i]
alist[i] = alist[j]
alist[j] = temp

меняет местами i-й и j-й элементы списка. Одно из значений будет переписано безо всякого временного хранилища.

В Python возможно одновременное присваивание. Оператор a,b = b,a даст тот же результат, что и два присваивания, сделанных в одно и то же время (см. рисунок 2). С использованием одновременного присваивания операция обмена займёт всего в одну строку.

Строки 5-7 в ActiveCode 1 производят обмен \(i\)-го и \((i+1)\)-го элементов, используя трёхступенчатую операцию, описанную выше. Заметьте, что для перестановки элементов мы также можем использовать одновременное присваивание.

Рисунок 2: Перестановка местами двух значений в Python

Следующий пример ActiveCode демонстрирует законченную функцию bubbleSort, работающую со списком, показанным выше.

Эта анимация показывает bubbleSort в действии.

Для большей детализации CodeLens позволит вам пройти по алгоритму шаг за шагом.

При анализе пузырьковой сортировки стоит отметить, что, вне зависимости от первоначального порядка элементов, для списка из \(n\) элементов будет сделан \(n-1\) проход. Таблица 1 показывает число сравнений при каждом проходе. Общее их количество - сумма первых \(n-1\) чисел. Напомним, что сумма первых \(n\) целых равна \(\frac{1}{2}n^{2} + \frac{1}{2}n\). Сумма первых \(n-1\) чисел равна \(\frac{1}{2}n^{2} + \frac{1}{2}n - n\), или после сокращения \(\frac{1}{2}n^{2} - \frac{1}{2}n\). Т.е. это по-прежнему \(O(n^{2})\) сравнений. В лучшем случае, когда список уже отсортирован, не будет сделано ни одной перестановки. Однако, для наихудшего случая каждое сравнение повлечёт за собой обмен. В среднем же обмен займёт половину времени.

Пузырьковая сортировка часто рассматривается как наиболее неэффективный сортировочный метод, поскольку она должна переставлять элементы до того, как станет известна их окончательная позиция. Эти “пустые” операции обмена весьма затратны. Однако, поскольку пузырьковая сортировка делает проход по всей несортированной части списка, она умеет то, что не могут большинство сортировочных алгоритмов. В частности, если во время прохода не было сделано ни одной перестановки, то мы знаем, что список уже отсортирован. Таким образом, алгоритм может быть модифицирован, чтобы останавливаться раньше, если обнаруживает, что задача выполнена. Т.е. для списков, которым нужно всего несколько проходов, пузырьковая сортировка имеет преимущество, поскольку умеет распознать сортированный список и остановиться. ActiveCode 2 демонстрирует эту модификацию, которую часто называют коротким пузырьком.

И, наконец, shortBubbleSort в CodeLens.