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

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

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

Пузырьковая сортировка (bubble sort) имеет следующие временные сложности:

Как работает пузырьковая сортировка

Алгоритм сравнивает соседние элементы и меняет их местами, если они в неправильном порядке. После каждого прохода самый большой элемент "всплывает" в конец массива.

#include <vector>
#include <iostream>

void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    
    // Внешний цикл: количество проходов
    for (int i = 0; i < n - 1; i++) {
        // Внутренний цикл: сравнение соседних элементов
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Обмен элементов
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

int main() {
    std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(arr);
    
    for (int x : arr) std::cout << x << " ";
    std::cout << std::endl;  // 11 12 22 25 34 64 90
    
    return 0;
}

Анализ временной сложности в деталях

Количество операций сравнения

Для массива из n элементов:

• Проход 1: n-1 сравнений
• Проход 2: n-2 сравнений
• Проход 3: n-3 сравнений
• ...
• Проход n-1: 1 сравнение

Общее количество сравнений:

(n-1) + (n-2) + (n-3) + ... + 1 = n(n-1)/2 = O(n²)

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

Если массив уже отсортирован, оптимизированная версия может завершиться за один проход:

void bubbleSortOptimized(std::vector<int>& arr) {
    int n = arr.size();
    
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;  // Флаг обмена
            }
        }
        
        // Если обменов не было, массив отсортирован
        if (!swapped) {
            break;  // Выходим из цикла
        }
    }
}

int main() {
    std::vector<int> arr = {1, 2, 3, 4, 5};  // Уже отсортирован
    bubbleSortOptimized(arr);  // O(n) сложность
    return 0;
}

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

Массив, отсортированный в обратном порядке, требует максимальное количество операций:

// Худший случай: {5, 4, 3, 2, 1}
// Проход 1: 4 обмена
// Проход 2: 3 обмена
// Проход 3: 2 обмена
// Проход 4: 1 обмен
// Итого: 4 + 3 + 2 + 1 = 10 операций = 5(5-1)/2

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

Практический пример анализа

#include <vector>
#include <chrono>
#include <iostream>

void bubbleSortWithCount(std::vector<int>& arr, long long& operations) {
    int n = arr.size();
    operations = 0;
    
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            operations++;  // Считаем операции сравнения
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

int main() {
    std::vector<int> arr = {5, 2, 8, 1, 9, 3};
    long long ops = 0;
    bubbleSortWithCount(arr, ops);
    
    std::cout << "Для массива из 6 элементов: " << ops << " операций" << std::endl;
    // 5(6-1)/2 = 15 операций
    
    return 0;
}

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

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

Почему пузырьковую сортировку редко используют

• Неэффективна на больших наборах данных (O(n²))
• Медленнее чем quicksort, mergesort, heapsort (они O(n log n))
• Только преимущество: простая для понимания и реализации
• Используется в образовании как первый алгоритм сортировки

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

// 1. Очень маленькие массивы (n < 10)
std::vector<int> small = {3, 1, 2};
bubbleSort(small);  // Приемлемо

// 2. Когда массив почти отсортирован (с оптимизацией)
std::vector<int> almost = {1, 2, 3, 5, 4, 6, 7};  // Один обмен
bubbleSortOptimized(almost);  // Близко к O(n)

// 3. Когда нужна стабильность (пузырьковая сортировка стабильна)
struct Item { int key; std::string value; };
std::vector<Item> items;
// Пузырьковая сортировка сохранит исходный порядок равных элементов

Ключевые моменты

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