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

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

Пузырьковая сортировка (Bubble Sort) — один из простейших алгоритмов сортировки, который многократно проходит по массиву, сравнивая соседние элементы и меняя их местами, если они находятся в неправильном порядке. Этот процесс повторяется до тех пор, пока массив не будет полностью отсортирован.

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

Худший случай (Worst Case)

В худшем случае, когда массив отсортирован в обратном порядке, алгоритму потребуется выполнить максимальное количество сравнений и обменов:

• Для массива из n элементов в первом проходе выполняется n-1 сравнение.
• Во втором проходе — n-2 сравнения, и так далее до последнего прохода с 1 сравнением.

Общее количество сравнений вычисляется по формуле суммы арифметической прогрессии:

Сравнения = (n-1) + (n-2) + ... + 1 = n(n-1)/2

Это составляет O(n²) операций сравнения.

Количество обменов в худшем случае также будет пропорционально n², так как каждый неправильно расположенный элемент потребует обмена. Таким образом, временная сложность в худшем случае составляет O(n²).

Лучший случай (Best Case)

В лучшем случае, когда массив уже отсортирован, пузырьковая сортировка с базовой реализацией все равно выполнит все проходы, поскольку она не отслеживает, были ли сделаны обмены. Однако, если добавить оптимизацию с флагом обменов (swap flag), алгоритм завершится после первого прохода, в котором не было ни одного обмена.

С оптимизацией:

• Количество сравнений: n-1 (один проход по массиву)
• Количество обменов: 0

Таким образом, временная сложность в лучшем случае с оптимизацией составляет O(n). Без оптимизации — O(n²).

Средний случай (Average Case)

В среднем случае, когда элементы расположены в случайном порядке, пузырьковая сортировка потребует примерно n(n-1)/4 сравнений и пропорциональное количество обменов. Это также приводит к квадратичной временной сложности O(n²).

Код реализации с оптимизацией

function bubbleSort(arr) {
    let n = arr.length;
    let swapped;
    
    for (let i = 0; i < n - 1; i++) {
        swapped = false;
        
        // Последние i элементов уже отсортированы
        for (let j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // Обмен элементов
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true;
            }
        }
        
        // Если обменов не было, массив отсортирован
        if (!swapped) break;
    }
    
    return arr;
}

// Пример использования
const array = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(array)); // [11, 12, 22, 25, 34, 64, 90]

Космическая сложность

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

Практическое применение и выводы

Несмотря на простоту реализации, пузырьковая сортировка редко используется на практике из-за своей низкой эффективности при больших объемах данных. Ее основные недостатки:

• Квадратичная временная сложность O(n²) в худшем и среднем случаях
• Медленная работа на больших массивах по сравнению с более эффективными алгоритмами (быстрая сортировка, сортировка слиянием и др.)
• Большое количество операций обмена даже в случаях, когда массив почти отсортирован

Однако у алгоритма есть некоторые преимущества:

• Простота понимания и реализации
• Стабильность — сохраняет порядок равных элементов
• Адаптивность — с оптимизацией работает быстрее на частично отсортированных данных
• Сортировка на месте — не требует дополнительной памяти

В современной фронтенд-разработке знание временной сложности алгоритмов важно для:

• Оптимизации работы с большими массивами данных на клиентской стороне
• Понимания принципов работы JavaScript-движков
• Решения алгоритмических задач на собеседованиях
• Выбора подходящего алгоритма для конкретной задачи

Для сортировки данных в реальных приложениях рекомендуется использовать встроенный метод Array.prototype.sort(), который в большинстве браузеров реализует эффективные алгоритмы (например, TimSort в Chrome и MergeSort в Firefox).