Сортировка пузырьком

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

Сортировка пузырьком — метод упорядочивания массива, при котором за несколько проходов соседние элементы сравниваются и меняются местами, если стоят в неправильном порядке.

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

Зачем это нужно

Упорядочить данные нужно постоянно: оценки по возрастанию, цены от дешёвых к дорогим, имена по алфавиту. В заданиях ОГЭ часто просят не написать сортировку с нуля, а проследить, что станет с массивом после одного-двух проходов пузырька. Если понимать механику обменов, такие пункты решаются за минуту без единой ошибки.

Идея попарных обменов

Один проход пузырька идёт слева направо и сравнивает каждую пару соседей: a[j] и a[j+1]. Если левый больше правого, их меняют местами. После полного прохода самый большой элемент гарантированно оказывается в самом конце — он «всплыл», как пузырёк воздуха в воде. Обмен двух переменных через временную:

если a[j] > a[j+1]:
    tmp   <- a[j]
    a[j]  <- a[j+1]
    a[j+1] <- tmp

Временная переменная tmp нужна, чтобы не затереть значение: если просто написать a[j] := a[j+1], старое a[j] потеряется. В Python есть короткая запись a[j], a[j+1] = a[j+1], a[j], но понимать обмен «через стакан» важно для блок-схем.

Вложенный цикл и число проходов

Один проход поднимает наверх только один максимум. Чтобы упорядочить весь массив из $n$ элементов, проходов нужно до $n-1$: после первого на месте старший элемент, после второго — два старших, и так далее. Отсюда два вложенных цикла — внешний считает проходы, внутренний сравнивает пары. Блок-схема:

для i от 0 до n-2:                (внешний: проходы)
    для j от 0 до n-2-i:         (внутренний: пары)
        если a[j] > a[j+1]:
            обменять a[j] и a[j+1]

[Начало] -> [i := 0]
  /i <= n-2 ?/ --нет--> [Конец]
   | да
  [j := 0]
  /j <= n-2-i ?/ --нет--> [i := i+1] (к внешней проверке)
   | да
  /a[j] > a[j+1] ?/ --нет--> [j := j+1] (к внутр. проверке)
   | да
  [обмен a[j],a[j+1]] -> [j := j+1] (к внутр. проверке)

Граница внутреннего цикла — n-2-i, а не n-2: после $i$ проходов последние $i$ элементов уже отсортированы, и трогать их незачем. Это маленькая оптимизация, но именно её любят спрашивать.

Сколько это сравнений

В худшем случае пузырёк делает примерно $\frac{n(n-1)}{2}$ сравнений — для каждого из $n$ элементов до $n$ шагов. Это растёт как $n^2$, поэтому на больших массивах пузырёк медленный:

$$ C = \sum_{i=1}^{n-1} (n - i) = \frac{n(n-1)}{2}. $$

Для $n = 5$ это $\frac{5 \cdot 4}{2} = 10$ сравнений в худшем случае — немного, поэтому для учебных массивов пузырёк вполне годится.

Как это работает

Оттрассируем сортировку массива из пяти чисел [5, 1, 4, 2, 8] по возрастанию, печатая массив после каждого прохода внешнего цикла.

a = [5, 1, 4, 2, 8]
n = len(a)

for i in range(n - 1):
    for j in range(n - 1 - i):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]   # обмен соседей
    print("После прохода", i + 1, ":", a)

print("Отсортировано:", a)

Вывод:

После прохода 1 : [1, 4, 2, 5, 8]
После прохода 2 : [1, 2, 4, 5, 8]
После прохода 3 : [1, 2, 4, 5, 8]
После прохода 4 : [1, 2, 4, 5, 8]
Отсортировано: [1, 2, 4, 5, 8]

Разберём первый проход вручную. Стартуем с [5, 1, 4, 2, 8]. Сравниваем $5$ и $1$ — меняем: [1, 5, 4, 2, 8]. Затем $5$ и $4$ — меняем: [1, 4, 5, 2, 8]. Затем $5$ и $2$ — меняем: [1, 4, 2, 5, 8]. Затем $5$ и $8$ — не меняем. Итог прохода: [1, 4, 2, 5, 8] — крупнейший элемент $8$ был и так в конце, а $5$ «всплыл» на предпоследнее место. После второго прохода массив уже упорядочен, а проходы 3 и 4 ничего не меняют — это нормально для пузырька без досрочного выхода.

Частые ошибки

Обмен без временной переменной. Запись a[j] := a[j+1]; a[j+1] := a[j] теряет одно значение: после первой строки оба элемента равны. Нужен tmp (или одновременный обмен в Python).
Выход за границу. Внутри сравнивают a[j] и a[j+1], поэтому j доходит только до предпоследнего индекса. Если j возьмёт последний, a[j+1] выйдет за массив.
Перепутать направление. Для возрастания меняют, когда a[j] > a[j+1]; для убывания — когда a[j] < a[j+1]. Неверный знак отсортирует в обратную сторону.
Один проход вместо многих. За один проход массив не упорядочится (всплывёт лишь один максимум). Нужен внешний цикл проходов.

Итоги

Пузырёк сравнивает соседей и меняет их местами, если порядок нарушен; обмен — через временную переменную.
За один проход наверх «всплывает» один максимум, поэтому нужен вложенный цикл и до $n-1$ проходов.
Граница внутреннего цикла n-2-i экономит сравнения: хвост уже отсортирован.
Сложность $\frac{n(n-1)}{2}$ сравнений — растёт как $n^2$, алгоритм медленный, но наглядный.
Трассировка по проходам — типичное задание ОГЭ; разбирайте обмены пара за парой.