Как работает сортировка пузырьком и её сложность

Как работает сортировка пузырьком? Какова её сложность?

Сортировка пузырьком многократно сравнивает соседние элементы и меняет их местами, если они стоят в неправильном порядке. После каждого прохода наибольший элемент «всплывает» в конец списка; средняя и худшая временная сложность алгоритма — O(n²).

Подробный ответ

Как работает алгоритм

Bubble sort проходит по списку, сравнивает соседние элементы и меняет их местами, если левый элемент больше правого. После первого прохода самый большой элемент оказывается в конце списка. Затем алгоритм повторяет проход для оставшейся неотсортированной части.

Реализация на Python

def bubble_sort(items: list[int]) -> list[int]:
    result = items.copy()
    length = len(result)

    for pass_index in range(length - 1):
        swapped = False

        for index in range(length - 1 - pass_index):
            if result[index] > result[index + 1]:
                result[index], result[index + 1] = result[index + 1], result[index]
                swapped = True

        if not swapped:
            break

    return result

Пример

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

Сложность

Случай	Временная сложность	Причина
Лучший	`O(n)`	Список уже отсортирован, и флаг `swapped` останавливает алгоритм после первого прохода
Средний	`O(n²)`	Нужно выполнять множество сравнений и перестановок
Худший	`O(n²)`	Список отсортирован в обратном порядке
Память	`O(1)`	Если сортировать исходный список на месте; в примере выше копия требует `O(n)`

Когда использовать

Сортировка пузырьком полезна для обучения, потому что её легко объяснить и реализовать. Для реальных больших наборов данных обычно используют более эффективные алгоритмы или встроенную сортировку языка, например sorted() в Python.

Как ответить на собеседовании

Bubble sort сравнивает соседние элементы и меняет их местами, пока список не станет отсортированным. После каждого прохода максимальный элемент оказывается в конце. Средняя и худшая сложность — O(n²), а улучшенный вариант с флагом отсутствия обменов работает за O(n) на уже отсортированном списке.