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

Сортировка пузырьком (Bubble Sort) имеет следующую временную сложность:

• Худший и средний случай: O(n²), где n — количество элементов. Алгоритм требует n-1 проходов по массиву, и на каждом проходе выполняется до n-1 сравнений и обменов.
• Лучший случай: O(n), достигается, если массив уже отсортирован. С оптимизированной версией алгоритм за один проход убедится в отсутствии обменов и завершит работу.

Пространственная сложность: O(1) — сортировка выполняется на месте, без использования дополнительной памяти.

Оптимизированная реализация на Java:

void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false; // Флаг оптимизации
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Обмен элементов
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        // Если на этом проходе не было обменов, массив отсортирован
        if (!swapped) {
            break;
        }
    }
}

Практическое применение: Из-за квадратичной сложности алгоритм неприменим для больших наборов данных. Используется только в учебных целях или для сортировки очень маленьких (до 10 элементов) или почти отсортированных массивов.