Как работает сортировка пузырьком: простое объяснение и примеры на Python

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

Основной принцип алгоритма: как "всплывают" элементы

Алгоритм последовательно сравнивает соседние элементы массива и меняет их местами, если они расположены в неправильном порядке. Более крупные элементы постепенно "всплывают" к концу массива, подобно пузырькам воздуха в воде — отсюда и название алгоритма.

flowchart TD A[Начало сортировки] --> B[Инициализация: i = 0] B --> C[Внутренний цикл: j = 0] C --> D[Сравнение arr#91;j#93; и arr#91;j+1#93;] D --> E{arr#91;j#93; > arr#91;j+1#93;?} E -->|Да| F[Обмен элементов местами] E -->|Нет| G[Переход к следующей паре: j++] F --> G G --> H{j < n-i-1?} H -->|Да| C H -->|Нет| I[Внешний цикл: i++] I --> J{i < n?} J -->|Да| B J -->|Нет| K[Сортировка завершена]

Пример базовой реализации на Python

def bubble_sort(arr):
    """
    Базовая реализация сортировки пузырьком
    Сложность: O(n²) во всех случаях
    Память: O(1) - сортировка на месте
    """
    n = len(arr)
    # Внешний цикл - количество проходов
    for i in range(n):
        # Внутренний цикл - сравнение соседних элементов
        for j in range(0, n - i - 1):
            # Сравниваем соседние элементы
            if arr[j] > arr[j + 1]:
                # Меняем местами, если порядок нарушен
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# Демонстрация работы
numbers = [64, 34, 25, 12, 22, 11, 90]
print("До сортировки:", numbers)
bubble_sort(numbers)
print("После сортировки:", numbers)

Визуализация процесса сортировки

Рассмотрим поэтапную сортировку массива [5, 3, 8, 4, 2]:

flowchart LR A[Проход 1:
5, 3, 8, 4, 2] --> B[3, 5, 8, 4, 2] B --> C[3, 5, 4, 8, 2] C --> D[3, 5, 4, 2, 8] E[Проход 2:
3, 5, 4, 2, 8] --> F[3, 4, 5, 2, 8] F --> G[3, 4, 2, 5, 8] H[Проход 3:
3, 4, 2, 5, 8] --> I[3, 2, 4, 5, 8] J[Проход 4:
3, 2, 4, 5, 8] --> K[2, 3, 4, 5, 8]

Анализ сложности алгоритма

Сценарий	Временная сложность	Объяснение
Худший случай	O(n²)	Массив отсортирован в обратном порядке
Средний случай	O(n²)	Случайный порядок элементов
Лучший случай	O(n)	Массив уже отсортирован (с оптимизацией)
Пространственная сложность	O(1)	Сортировка на месте, без дополнительной памяти

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

Добавление флага проверки обменов сокращает количество итераций для частично упорядоченных массивов. Также уменьшаем диапазон внутреннего цикла после каждого прохода.

flowchart TD A[Начало оптимизированной сортировки] --> B[swapped = True, n = len#40;arr#41;] B --> C{swapped == True?} C -->|Нет| D[Сортировка завершена] C -->|Да| E[swapped = False] E --> F[Внутренний цикл: i = 0 to n-1] F --> G{arr#91;i#93; > arr#91;i+1#93;?} G -->|Да| H[Обмен элементов] H --> I[swapped = True] I --> J[Следующий элемент] G -->|Нет| J J --> K{i < n-1?} K -->|Да| F K -->|Нет| L[n -= 1] L --> C

Улучшенная версия кода

def optimized_bubble_sort(arr):
    """
    Оптимизированная версия сортировки пузырьком
    - Прерывается если массив уже отсортирован
    - Уменьшает диапазон сравнений после каждого прохода
    """
    n = len(arr)
    swapped = True

    # Продолжаем пока происходят обмены
    while swapped:
        swapped = False
        for i in range(n - 1):
            if arr[i] > arr[i + 1]:
                # Обмен элементов
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        # Уменьшаем диапазон, т.к. последний элемент уже на месте
        n -= 1

    return arr

# Тестирование на уже отсортированном массиве
sorted_array = [1, 2, 3, 4, 5]
optimized_bubble_sort(sorted_array)  # Завершится после первого прохода

Дополнительная оптимизация — запоминание последнего обмена

def super_optimized_bubble_sort(arr):
    """
    Супер-оптимизированная версия с запоминанием последнего обмена
    """
    n = len(arr)
    while n > 1:
        new_n = 0
        for i in range(1, n):
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]
                new_n = i
        n = new_n  # Все элементы после new_n уже отсортированы
    return arr

Сравнение производительности

Размер массива	Базовая версия	Оптимизированная версия	Выигрыш
100 элементов	~10,000 операций	~5,000 операций	2x
1,000 элементов	~1,000,000 операций	~500,000 операций	2x
Уже отсортированный массив	O(n²)	O(n)	n раз

Преимущества и недостатки

graph LR A[Сортировка пузырьком] --> B[Преимущества] A --> C[Недостатки] B --> D[Простота реализации] B --> E[Сортировка на месте] B --> F[Стабильность] B --> G[Учебный алгоритм] C --> H[Медленная O#40;n²#41;] C --> I[Непрактична для больших данных] C --> J[Много избыточных сравнений]

Плюсы:

🎓 Простота понимания и реализации — идеально для обучения
💾 Не требует дополнительной памяти — сортировка на месте (in-place)
🔄 Стабильность — сохраняет порядок равных элементов
⚡ Эффективна для почти отсортированных данных — с оптимизацией

Минусы:

🐌 Квадратичная временная сложность O(n²) — медленная для больших данных
📊 Непрактична для больших наборов данных — более 1000 элементов
🔄 Много избыточных сравнений — даже когда массив уже отсортирован
🏎️ Проигрывает современным алгоритмам — QuickSort, MergeSort, TimSort

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

Области применения

Обучение программированию — первый алгоритм сортировки для изучения
Небольшие наборы данных — до 50-100 элементов
Частично отсортированные данные — с оптимизированной версией
Встроенные системы — где важна простота, а не скорость

Сравнение с другими алгоритмами

# Сравнение времени выполнения для 1000 элементов
import time
import random

data = [random.randint(1, 1000) for _ in range(1000)]

# Сортировка пузырьком
start = time.time()
bubble_sort(data.copy())
bubble_time = time.time() - start

# Встроенная сортировка Python
start = time.time()
sorted(data.copy())
builtin_time = time.time() - start

print(f"Пузырьковая: {bubble_time:.4f} сек")
print(f"Встроенная: {builtin_time:.4f} сек")
print(f"Разница: {bubble_time/builtin_time:.1f}x")