Какая сложность сортировки пузырьком?

Сложность сортировки пузырьком

Сортировка пузырьком (Bubble Sort) — это один из самых простых алгоритмов сортировки, но и один из самых неэффективных. Давайте разберём его сложность детально.

Временная сложность

Худший случай (worst case): O(n²)

Это происходит, когда массив отсортирован в обратном порядке:

# Массив: [5, 4, 3, 2, 1]
# Нужно сделать максимум n-1 проходов
# На каждом проходе сравниваем n элементов
# Всего операций: n × (n-1) / 2 ≈ n²

Средний случай (average case): O(n²)

В среднем случае тоже O(n²), потому что нам нужно переставить в среднем половину элементов, что всё равно даёт квадратичную сложность.

Лучший случай (best case): O(n)

Когда массив уже отсортирован! Оптимизированная версия может обнаружить это и выйти после первого прохода:

def bubble_sort_optimized(arr):
    n = len(arr)
    for i in range(n):
        swapped = False  # Флаг для отслеживания обменов
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        if not swapped:  # Если обменов не было — массив отсортирован
            break
    return arr

# Для уже отсортированного массива: O(n)
arr = [1, 2, 3, 4, 5]
bubble_sort_optimized(arr)  # Сделает только 1 проход

Во втором примере временная сложность падает до O(n), потому что на первом же проходе обнаружится, что обменов не было.

Основная версия пузырька

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):              # Внешний цикл: n итераций
        for j in range(n - i - 1):  # Внутренний цикл: n-1, n-2, ..., 1 итераций
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# Анализ:
# Проход 1: n-1 сравнений
# Проход 2: n-2 сравнений
# ...
# Проход n: 0 сравнений
# Всего: (n-1) + (n-2) + ... + 0 = n×(n-1)/2 ≈ O(n²)

Пространственная сложность

O(1) — константная!

Пузырьком сортирует на месте (in-place), используя только переменные для индексов и временного хранения при обмене:

def bubble_sort(arr):
    # Не создаём новый массив
    # Не используем дополнительные структуры данных
    # Только i, j, temp — O(1) дополнительной памяти

Это очень хорошее свойство, но оно не компенсирует плохую временную сложность.

Наглядный пример

Для массива из 5 элементов [5, 2, 8, 1, 9]:

Проход 1:
[5, 2, 8, 1, 9] → сравниваем 5 и 2 → [2, 5, 8, 1, 9]
[2, 5, 8, 1, 9] → сравниваем 5 и 8 → [2, 5, 8, 1, 9]
[2, 5, 8, 1, 9] → сравниваем 8 и 1 → [2, 5, 1, 8, 9]
[2, 5, 1, 8, 9] → сравниваем 8 и 9 → [2, 5, 1, 8, 9]
# 4 сравнения, 2 обмена

Проход 2:
[2, 5, 1, 8, 9] → [2, 5, 1, 8, 9]
[2, 5, 1, 8, 9] → [2, 1, 5, 8, 9]
[2, 1, 5, 8, 9] → [2, 1, 5, 8, 9]
# 3 сравнения

Проход 3:
[2, 1, 5, 8, 9] → [1, 2, 5, 8, 9]
[1, 2, 5, 8, 9] → [1, 2, 5, 8, 9]
# 2 сравнения

Проход 4:
[1, 2, 5, 8, 9] → [1, 2, 5, 8, 9]
# 1 сравнение

Всего: 4 + 3 + 2 + 1 = 10 операций сравнения
Теоретически: 5×4/2 = 10 ✓

Почему O(n²) — это плохо?

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

import time

# Для n = 10,000:
n = 10_000

# Bubble Sort: n² = 100,000,000 операций ~1 сек
# Quick Sort: n log n = 132,877 операций ~0.001 сек
# Tim Sort (Python): n log n = 132,877 операций ~0.0005 сек

# Для n = 100,000:
n = 100_000

# Bubble Sort: n² = 10,000,000,000 операций ~100 сек!
# Quick Sort: n log n = 1,660,964 операций ~0.01 сек
# Tim Sort: n log n = 1,660,964 операций ~0.005 сек

Пузырьком в 10,000 раз медленнее для больших массивов!

Когда пузырьком приемлем?

✅ Используй пузырьком только если:

• Массив очень маленький (< 50 элементов)
• Массив почти отсортирован (с оптимизацией O(n))
• Учишься (это просто для понимания)
• Доказываешь какой-то теоретический результат

❌ Никогда не используй в production:

• Используй встроенный sort() (Tim Sort — O(n log n))
• Или sorted() функцию Python
• Для специальных случаев — Quick Sort, Merge Sort, Heap Sort

Python встроенные варианты

# ✅ Правильно: используем встроенную сортировку
arr = [5, 2, 8, 1, 9]
arr.sort()  # Tim Sort, O(n log n)

sorted_arr = sorted(arr)  # Тоже Tim Sort

# ❌ Неправильно: реализовывать пузырьком самостоятельно
def bubble_sort(arr):  # Медленнее в 1000+ раз!
    # ...

Сравнительная таблица

Заключение

Сложность пузырька:

• Худший/средний: O(n²) — квадратичная, очень медленно
• Лучший: O(n) — если отсортирован (с оптимизацией флага)
• Память: O(1) — сортирует на месте

В реальном коде используй встроенный sort() Python — это Tim Sort с O(n log n), который оптимизирован и адаптирован к разным типам данных.