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

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

В реальных проектах обычно используют sorted() или .sort(), но пузырьковая сортировка хорошо показывает вложенные циклы, сравнение элементов, обмен значений и цену неэффективного алгоритма

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

По этой теме полезно отдельно посмотреть Аннотации типов для декораторов в Python, чтобы расширить контекст и сравнить подходы

Идея алгоритма

Представьте список:

[5, 2, 9, 1]

Алгоритм идет слева направо и сравнивает соседей:

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

Отсюда и название: большие значения как будто всплывают к концу списка

Базовая реализация

numbers = [5, 2, 9, 1]

for i in range(len(numbers)):
    for j in range(0, len(numbers) - 1 - i):
        if numbers[j] > numbers[j + 1]:
            numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]

print(numbers)

Вывод:

[1, 2, 5, 9]

Внешний цикл отвечает за проходы по списку, внутренний — за сравнение соседних элементов

Разбор границ цикла

Внутренний цикл написан так:

for j in range(0, len(numbers) - 1 - i):

len(numbers) - 1 нужен, чтобы можно было обратиться к numbers[j + 1] и не выйти за границу списка

- i нужен, потому что после каждого прохода один самый большой элемент уже стоит справа на своем месте

Без - i алгоритм все равно может работать, но будет делать лишние сравнения

Увидеть проходы сортировки

Добавим вывод после каждого прохода

numbers = [5, 2, 9, 1]

for i in range(len(numbers)):
    for j in range(0, len(numbers) - 1 - i):
        if numbers[j] > numbers[j + 1]:
            numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]

    print(f'после прохода {i + 1}: {numbers}')

Примерный вывод:

после прохода 1: [2, 5, 1, 9]
после прохода 2: [2, 1, 5, 9]
после прохода 3: [1, 2, 5, 9]
после прохода 4: [1, 2, 5, 9]

Так проще увидеть, как элементы постепенно встают на места

Подсчет обменов

numbers = [5, 2, 9, 1]
swaps = 0

for i in range(len(numbers)):
    for j in range(0, len(numbers) - 1 - i):
        if numbers[j] > numbers[j + 1]:
            numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
            swaps += 1

print(numbers)
print(f'обменов: {swaps}')

Подсчет обменов помогает понять, насколько список был далек от отсортированного состояния

Ранний выход

Если за проход не было ни одного обмена, список уже отсортирован

numbers = [1, 2, 3, 4]

for i in range(len(numbers)):
    swapped = False

    for j in range(0, len(numbers) - 1 - i):
        if numbers[j] > numbers[j + 1]:
            numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
            swapped = True

    if not swapped:
        break

print(numbers)

Это не превращает пузырьковую сортировку в лучший алгоритм, но убирает лишние проходы на уже отсортированных данных

Функция bubble_sort

def bubble_sort(values):
    result = values.copy()

    for i in range(len(result)):
        swapped = False

        for j in range(0, len(result) - 1 - i):
            if result[j] > result[j + 1]:
                result[j], result[j + 1] = result[j + 1], result[j]
                swapped = True

        if not swapped:
            break

    return result

numbers = [5, 2, 9, 1]

print(bubble_sort(numbers))
print(numbers)

Функция возвращает новый список и не меняет исходный. Для учебного кода это полезно: легче проверить, что происходит с данными

Сортировка строк

words = ['banana', 'apple', 'cherry']
print(bubble_sort(words))

Python умеет сравнивать строки в алфавитном порядке. Но в реальных задачах для строк, регистра и русских букв могут понадобиться дополнительные правила сортировки

Почему в проектах используют sorted

Встроенная сортировка Python быстрее, надежнее и удобнее

numbers = [5, 2, 9, 1]

print(sorted(numbers))
print(numbers)

sorted() возвращает новый список

.sort() меняет список на месте

numbers.sort()
print(numbers)

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

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

• выходить за границу списка при обращении к numbers[j + 1]
• забывать - i во внутреннем цикле
• путать sorted() и .sort()
• менять исходный список, хотя ожидалась копия
• использовать пузырек в реальной задаче вместо встроенной сортировки
• не проверять пустой список и список из одного элемента

Практика

Сделайте четыре задания

1. Добавьте вывод каждого сравнения
2. Посчитайте количество сравнений и обменов
3. Отсортируйте список строк
4. Сравните результат bubble_sort(numbers) и sorted(numbers)

Что читать дальше

Для понимания вложенности алгоритма повторите Вложенные циклы в Python

Для базовой работы со списками пригодится Шпаргалка по Python

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

Алгоритм полезен для обучения, потому что показывает вложенные циклы, индексы, обмен значений и оптимизацию через ранний выход

В рабочих задачах почти всегда берите sorted() или .sort()