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

Временная сложность пузырьковой сортировки:

• Худший и средний случай: O(n²), где n — количество элементов в массиве. Это происходит из-за вложенных циклов: внешний проходит n-1 раз, а внутренний в худшем случае делает n-i-1 сравнений и возможных обменов. Суммарно количество операций пропорционально n*(n-1)/2.
• Лучший случай (массив уже отсортирован): O(n). При добавлении флага оптимизации (swapped) алгоритм за одну полную проходку по массиву обнаружит, что обменов не было, и завершит работу.

Пространственная сложность: O(1), так как сортировка выполняется на месте (in-place) и не требует дополнительной памяти, пропорциональной размеру входных данных (не считая небольшого постоянного объема для переменных).

Оптимизированная реализация на Python, демонстрирующая сложность:

def bubble_sort(arr):
    """Сортировка пузырьком с оптимизацией."""
    n = len(arr)
    # Внешний цикл: O(n) итераций
    for i in range(n):
        swapped = False
        # Внутренний цикл: O(n-i) итераций
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                # Обмен элементов - операция O(1)
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # Если обменов не было, массив отсортирован -> выход за O(n)
        if not swapped:
            break
    return arr

# Пример вызова
unsorted_list = [64, 34, 25, 12, 22, 11, 90]
sorted_list = bubble_sort(unsorted_list.copy())
print(f"Отсортированный список: {sorted_list}")

Практический вывод: Пузырьковая сортировка — наглядный учебный алгоритм, но на практике для больших данных почти всегда выбирают более эффективные алгоритмы (QuickSort, MergeSort, Timsort в Python), так как O(n²) становится непозволительно медленным при росте n.