Алгоритмы на Python

Сортировка пузырьком (bubble sort) в Python

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

  • Средний
  • Чтение: 2 мин
  • Примеров для запуска: 1

Введение

Какую задачу это решает

Сортировка повсюду, и понимание того, как она работает, помогает рассуждать о скорости. Пузырьковую сортировку легче всего проследить шаг за шагом, поэтому она обычно служит первым примером, хотя настоящие программы используют более быстрые.

Пример из жизни

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

От построения детей к коду
result[index] > result[index + 1]👫 Впереди стоит более высокий?
result[index], result[index + 1] = ...🔄 Поменять двух соседей местами
for end in range(len(result) - 1, 0, -1):🚶 Снова пройти ряд, каждый раз на одного короче
if not swapped: break✅ За весь проход ни одного обмена: ряд отсортирован
После каждого прохода наибольшее оставшееся значение стоит на своём месте.
Одним предложением

Пузырьковая сортировка многократно проходит по списку, меняя местами соседние элементы, стоящие в неверном порядке, пока полный проход не обойдётся без обменов; в общем случае она занимает время O(n²).

Главное

  1. result = values.copy() сортирует копию, поэтому список вызывающего не меняется.
  2. if result[index] > result[index + 1]: меняет местами пару в неверном порядке.
  3. end уменьшается после каждого прохода, потому что наибольшие значения уже в конце.
  4. if not swapped: break останавливается раньше, если проход обошёлся без обменов, поэтому отсортированный ввод заканчивается за один проход.

Когда это нужно?

  • Изучение того, как работает сортировка сравнениями.
  • Крошечные списки в учебных инструментах и визуализациях.
  • Проверка за один проход, отсортирован ли список.

Когда это не нужно

  • Любая настоящая программа: sorted() и list.sort() гораздо быстрее (O(n log n)) и проверены.
  • Списки больше нескольких сотен элементов: число сравнений растёт как квадрат длины.

Визуализация: Сортировка пузырьком (bubble sort) в Python

O(n²)

Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.

Пример кода

Запустить код →
main.py
def bubble_sort(values):
    result = values.copy()
    for end in range(len(result) - 1, 0, -1):
        swapped = False
        for index in range(end):
            if result[index] > result[index + 1]:
                result[index], result[index + 1] = result[index + 1], result[index]
                swapped = True
        if not swapped:
            break
    return result

print(bubble_sort([5, 1, 4, 2, 8]))
Получить кнопку запуска для этого примера

Результат выполнения

[1, 2, 4, 5, 8]

Разбор кода

После каждого прохода самое большое значение неотсортированной части уже стоит на своём окончательном месте, поэтому следующий проход короче на один элемент. Переменная swapped показывает, был ли обмен за проход. Если обменов не было, список уже отсортирован и цикл останавливается раньше. В худшем случае сложность O(n²), поэтому для больших объёмов данных алгоритм не подходит.

Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.

Упражнения для практики

Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.

  1. Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
  2. Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
  3. Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Запустить в компиляторе Python →

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

Выход на один индекс дальше

result[index + 1] выходит за конец, когда index доходит до последней позиции.

Ошибка
for index in range(len(result)):
    if result[index] > result[index + 1]:
Исправление
for index in range(end):
    if result[index] > result[index + 1]:

Закончили этот урок?

Отметьте его как изученный, чтобы следить за прогрессом.

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи