Bubble sort

Определение#

Пузырьковая сортировка (Bubble sort) - это алгоритм сортировки, суть которого заключается во всплывании элемента на нужную позицию, путём сравнения текущего элемента с соседним.

    class Solution:
        def sortColors(self, nums: List[int]) -> None:
            n = len(nums)
            for i in range(n):
                for j in range(n - i - 1):
                    if nums[j] > nums[j+1]:
                        nums[j], nums[j+1] = nums[j+1], nums[j]

Зачем нужна#

Bubble Sort считается «учебным» алгоритмом: из‑за своей низкой эффективности он почти не применяется в реальных проектах, но идеально подходит для первого знакомства с миром алгоритмов и понятием сложности O(n²).

Он помогает понять базовые принципы перебора данных, работы циклов и механизма обмена значений (swap).

Основное преимущество — предельная простота реализации и отсутствие необходимости в дополнительной памяти.

Пояснение#

1) В пузырьковой сортировке за один внешний проход самый большой элемент всплывает в конец ещё неотсортированной части массива.

2) После первого прохода последний элемент 100% находится на своём месте.

3) Значит, на i-м проходе последние i элементы трогать уже не нужно - они отсортированы.

Неотсортированная часть на i-м проходе - это элементы от 0 до N - i - 1 включительно.
Для сортировки по возрастанию, необходимо изменить знак > на знак <.

Интуитивно про конструкцию N - i - 1#

На 1‑м проходе (i = 0) внутренний цикл идёт j in range(N - 0 - 1) — до предпоследнего элемента, последний «выплывает».
На 2‑м проходе (i = 1) уже j in range(N - 1 - 1) — предпоследний тоже на месте, проверять его с концом больше не нужно.
И так далее, каждый раз диапазон сужается справа.

Характеристики#

Характеристика	Значение	Пояснение
Среднее время	`O(n²)`	Эффективность быстро падает с ростом данных
Лучшее время	`O(n)`	Если массив уже отсортирован (при наличии оптимизации)
Память (доп.)	`O(1)`	Сортировка происходит «на месте» (in-place)
Стабильный?	Да	Не меняет порядок равных элементов