Сложность алгоритмов и пузырьковая сортировка

Вы уже умеете сортировать список одной строкой: sorted(numbers) или numbers.sort() справятся с чем угодно, от пяти чисел до миллиона. Тогда зачем разбираться, как устроена сортировка внутри? Во-первых, это частый вопрос на технических собеседованиях. Во-вторых, это учит смотреть на любой код с вопросом "а что будет, если данных станет намного больше". В этом уроке вы научитесь сравнивать алгоритмы по скорости и разберёте первый алгоритм сортировки — пузырьковый.

Как сравнивать скорость алгоритмов

Представьте, что вы ищете имя в бумажном телефонном справочнике. Если вы точно знаете номер страницы — открываете сразу нужный разворот, и не важно, сколько всего страниц: десять или тысяча, действие одно и то же. А если вы листаете справочник подряд, страницу за страницей, пока не наткнётесь на нужную фамилию — в справочнике толщиной в тысячу страниц вы потратите в сто раз больше времени, чем в справочнике на десять страниц. Именно такую закономерность важно измерять — не секунды на конкретном компьютере, а то, как действий становится больше при росте данных.

В программировании такую оценку называют временной сложностью алгоритма и записывают в нотации Big O (читается "О большое"). Big O показывает не точное число операций, а то, как оно растёт вместе с размером входных данных n. Разберём три частых случая на коротких примерах.

numbers = [4, 8, 15, 16, 23, 42]
first = numbers[0]

• numbers[0] — обращение по индексу. Python сразу знает, где лежит нулевой элемент, и берёт его за один шаг — независимо от того, шесть элементов в списке или шесть миллионов.

Это и есть O(1), константная сложность: число действий не зависит от размера данных вообще.

total = 0
for number in numbers:
    total = total + number

• for number in numbers: — цикл проходит по каждому элементу списка ровно один раз.
• total = total + number — на каждом шаге выполняется одно и то же простое действие.

Если элементов n, тело цикла выполнится n раз — это O(n), линейная сложность: список вдвое длиннее — работы вдвое больше.

for a in numbers:
    for b in numbers:
        pair = (a, b)

• for a in numbers: — внешний цикл проходит по всем n элементам.
• for b in numbers: — и для каждого значения a снова проходит по всем n элементам — это вложенный цикл.

Тело внутреннего цикла выполнится n × n = n² раз — это O(n²), квадратичная сложность: список длиннее в 10 раз — действий больше в 100 раз.

Идея пузырьковой сортировки

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

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

Разберём на списке [5, 3, 8, 1, 2], сравнивая соседей слева направо:

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

Переводим идею в код

Чтобы повторить проходы, а внутри каждого прохода сравнить всех соседей, нужны два вложенных цикла: внешний считает проходы, внутренний сравнивает пары.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

numbers = [5, 3, 8, 1, 2]
print(bubble_sort(numbers))

Разберём построчно:

• def bubble_sort(arr): — функция принимает список arr, который нужно отсортировать по возрастанию.
• n = len(arr) — запоминаем длину списка один раз, чтобы не считать её заново на каждом шаге.
• for i in range(n - 1): — внешний цикл считает проходы. Их нужно n - 1: как только n - 1 чисел встали на места, последнее оказывается на месте само собой.
• for j in range(n - 1 - i): — внутренний цикл сравнивает соседей: элемент j и элемент j + 1. Верхняя граница уменьшается на i с каждым проходом, потому что i последних элементов уже "всплыли".
• if arr[j] > arr[j + 1]: — если левый сосед больше правого, пара стоит не по порядку.
• arr[j], arr[j + 1] = arr[j + 1], arr[j] — обмен без временной переменной: справа Python собирает пару текущих значений (arr[j + 1], arr[j]), а затем раскладывает её по именам слева в том же порядке. Так arr[j] получает старое значение arr[j + 1], а arr[j + 1] — старое значение arr[j]: два значения меняются местами одной строкой.
• return arr — после всех проходов список отсортирован, функция возвращает его.
• print(bubble_sort(numbers)) — выведет [1, 2, 3, 5, 8].

Оптимизация: выйти раньше, если список уже отсортирован

Список [1, 2, 3, 4, 5] уже отсортирован, но функция из прошлого раздела всё равно честно выполнит все n - 1 проходов, ни разу не поменяв элементы местами — это лишняя работа. Хочется, чтобы алгоритм умел заметить: "за целый проход ни одного обмена не было — список уже готов".

Для этого заводят флаг обменов — переменную, которая в начале каждого прохода сбрасывается в False, а становится True, как только произошёл хотя бы один обмен. Если после внутреннего цикла флаг остался False, значит, обменов не было, и можно завершить сортировку досрочно.

def bubble_sort_optimized(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

print(bubble_sort_optimized([1, 2, 3, 4, 5]))
print(bubble_sort_optimized([5, 3, 8, 1, 2]))

• swapped = False — перед началом очередного прохода считаем, что обменов ещё не было.
• arr[j], arr[j + 1] = arr[j + 1], arr[j] и следом swapped = True — как только реально произошёл хотя бы один обмен, отмечаем это флагом.
• if not swapped: — проверка после внутреннего цикла: если за весь проход флаг так и остался False, обменов не было ни разу.
• break — прерывает внешний цикл: дальнейшие проходы точно ничего не изменят, список уже отсортирован.
• Первый вызов bubble_sort_optimized([1, 2, 3, 4, 5]) сделает один проход, не найдёт ни одного обмена и сразу выйдет — напечатает [1, 2, 3, 4, 5].
• Второй вызов отработает как обычно и напечатает [1, 2, 3, 5, 8], потому что обмены там будут происходить до последнего прохода.

Это меняет сложность в лучшем случае: для уже отсортированного списка алгоритм с флагом делает один проход — O(n) вместо O(n²). В среднем и худшем случаях сложность остаётся O(n²): элементы всё равно приходится "протаскивать" через значительную часть списка.

Сложность по памяти: почему это in-place сортировка

Кроме времени, алгоритмы оценивают ещё по памяти: сколько дополнительного места им нужно сверх исходных данных. Аналогия: чтобы переставить книги на одной полке по алфавиту, вторая полка не нужна — книги просто меняются местами прямо на своей полке.

Функции bubble_sort и bubble_sort_optimized переставляют элементы прямо внутри переданного списка arr, не создавая новый список. Такой подход называют сортировкой на месте, или in-place: дополнительно расходуется лишь пара переменных для индексов и флага — это не зависит от размера списка, то есть O(1) по памяти. Это то же различие, что между .sort() (сортирует на месте, ничего не возвращает) и sorted() (создаёт и возвращает новый список, оставляя исходный без изменений) — второму нужна память под копию, то есть O(n).

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