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

1️⃣ Как кратко ответить

Пузырьковая сортировка имеет временную сложность O(n^2) в худшем и среднем случаях, и O(n) в лучшем случае, когда массив уже отсортирован.

2️⃣ Подробное объяснение темы

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

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

• Худший случай (O(n^2)): Происходит, когда массив отсортирован в обратном порядке. Алгоритм должен выполнить n-1 проходов, и на каждом проходе он выполняет n-i-1 сравнений, где i — номер текущего прохода. Это приводит к квадратичной временной сложности.

• Средний случай (O(n^2)): В среднем случае также требуется O(n^2) операций, так как элементы расположены в случайном порядке, и алгоритм должен выполнить множество сравнений и обменов.

• Лучший случай (O(n)): Если массив уже отсортирован, алгоритм выполнит только один проход по массиву, чтобы убедиться, что он отсортирован. Это возможно благодаря использованию флага, который отслеживает, были ли выполнены обмены на текущем проходе. Если обменов не было, алгоритм завершает работу.

Пример кода

#include <iostream>
#include <vector>
​
// Функция для выполнения пузырьковой сортировки
void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    bool swapped; // Флаг для отслеживания обменов
​
    // Внешний цикл для каждого прохода
    for (int i = 0; i < n - 1; ++i) {
        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> data = {64, 34, 25, 12, 22, 11, 90};
​
    // Выводим исходный массив
    std::cout << "Unsorted array: ";
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
​
    // Выполняем пузырьковую сортировку
    bubbleSort(data);
​
    // Выводим отсортированный массив
    std::cout << "Sorted array: ";
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
​
    return 0;
}

Объяснение кода

• std::vector<int>& arr: Используем вектор для хранения массива, который будет сортироваться.
• bool swapped: Флаг, который отслеживает, были ли выполнены обмены на текущем проходе. Если нет, то массив уже отсортирован, и можно завершить выполнение.
• Внешний цикл for (int i = 0; i < n - 1; ++i): Проходит по каждому элементу массива, уменьшая количество необходимых сравнений на каждом проходе.
• Внутренний цикл for (int j = 0; j < n - i - 1; ++j): Сравнивает соседние элементы и меняет их местами, если они находятся в неправильном порядке.
• std::swap(arr[j], arr[j + 1]): Меняет местами элементы, если текущий элемент больше следующего.
• if (!swapped) break;: Если на текущем проходе не было обменов, массив уже отсортирован, и выполнение можно завершить досрочно.