Ответ
Временная сложность пузырьковой сортировки:
- Худший и средний случай: O(n²) — требуется два вложенных цикла по n элементов.
- Лучший случай: O(n) — достигается при использовании флага, который прерывает алгоритм, если за проход не было ни одного обмена (массив уже отсортирован).
Реализация на C++ с оптимизацией:
#include <algorithm> // для std::swap
void bubbleSort(int arr[], int n) {
bool swapped;
for (int i = 0; i < n - 1; ++i) {
swapped = false;
// Последние i элементов уже на месте
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;
}
}
}Почему O(n²)? Количество сравнений в худшем случае — это сумма арифметической прогрессии: (n-1) + (n-2) + ... + 1 = n(n-1)/2, что асимптотически равно O(n²).
