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

Сортировка пузырьком имеет временную сложность O(n²) в худшем и среднем случае, и O(n) в лучшем (если массив уже отсортирован и используется оптимизация с флагом). Пространственная сложность — O(1), так как сортировка выполняется на месте.

Алгоритм проходит по массиву, попарно сравнивая соседние элементы и меняя их местами, если они расположены в неправильном порядке. После каждого прохода самый большой элемент «всплывает» в конец. В классическом варианте без оптимизации всегда выполняется n-1 проходов, каждый проход — от n-1 до 1 сравнений, что даёт сумму ~n²/2, то есть O(n²).

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {          // n-1 проходов
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++) {  // количество сравнений уменьшается
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;  // если за проход не было обменов, массив отсортирован
    }
}

С оптимизацией (флаг swapped) в лучшем случае выполняется один проход за O(n). Без неё лучший случай — тоже O(n²), потому что внешний цикл всё равно сделает n-1 итераций.

На практике пузырьковую сортировку редко используют из-за низкой эффективности. Однако она полезна для обучения: наглядно показывает работу вложенных циклов и понятие устойчивости (она стабильна — равные элементы не меняют порядок).