🌊 Сортировка пузырьком (Bubble Sort)

Алгоритм пузырьковой сортировки — один из самых простых для понимания. Он многократно проходит по списку, сравнивая соседние элементы и меняя их местами, если они стоят в неверном порядке. За каждый проход «наибольший» элемент всплывает вверх — как пузырёк в воде.

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

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

🔹 Пример: сортировка списка a = [5, 1, 4, 2, 8]

Первый проход:

[5, 1, 4, 2, 8] → [1, 5, 4, 2, 8]  # 5 > 1, меняем
[1, 5, 4, 2, 8] → [1, 4, 5, 2, 8]  # 5 > 4, меняем
[1, 4, 5, 2, 8] → [1, 4, 2, 5, 8]  # 5 > 2, меняем
[1, 4, 2, 5, 8] → [1, 4, 2, 5, 8]  # 5 < 8, не меняем

Самый большой элемент 8 «всплыл» на своё место.

Второй проход:

[1, 4, 2, 5, 8] → [1, 4, 2, 5, 8]  # 1 < 4
[1, 4, 2, 5, 8] → [1, 2, 4, 5, 8]  # 4 > 2, меняем
[1, 2, 4, 5, 8] → [1, 2, 4, 5, 8]  # 4 < 5

Теперь второй по величине элемент 5 на месте.

Третий проход:

[1, 2, 4, 5, 8] → [1, 2, 4, 5, 8]  # 1 < 2
[1, 2, 4, 5, 8] → [1, 2, 4, 5, 8]  # 2 < 4

Список уже отсортирован, но алгоритм этого не знает и продолжает.

Четвёртый проход:

[1, 2, 4, 5, 8] → [1, 2, 4, 5, 8]

🧩 Визуализация

Каждый проход «выталкивает» один элемент на своё место справа. После первого прохода — 1 элемент на месте, после второго — 2, и так далее.

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

a = [1, 7, -3, 9, 0, -67, 34, 12, 45, 1000, 6, 8, -2, 99]
n = len(a)

for i in range(n - 1):
    for j in range(n - 1 - i):
        if a[j] > a[j + 1]:                  # если элементы стоят неправильно
            a[j], a[j + 1] = a[j + 1], a[j]  # меняем местами

print('Отсортированный список:', a)

Результат:

Отсортированный список: [-67, -3, -2, 0, 1, 6, 7, 8, 9, 12, 34, 45, 99, 1000]

⚙️ Оптимизация алгоритма

Если за один проход не было ни одного обмена — значит, список уже отсортирован. В этом случае можно прервать работу алгоритма заранее, используя флаг и оператор break.

a = [1, 7, -3, 9, 0, -67, 34, 12, 45, 1000, 6, 8, -2, 99]
n = len(a)

for i in range(n - 1):
    swapped = False  # флаг: были ли обмены
    for j in range(n - 1 - i):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]
            swapped = True
    if not swapped:
        break  # если обменов не было, список отсортирован

print('Отсортированный список:', a)