Учебник по информатике и математике
Темы
C++
Основы языка
Сортировка пузырьком
Оглавление:
На физкультуре учитель просит класс выстроиться по росту, от самого низкого к самому высокому, но сам никого не переставляет. Правило одно: сравни свой рост с соседом справа и, если ты выше, поменяйтесь местами. Пара за парой ребята проходят по шеренге от начала до конца, и самый высокий оказывается последним. Еще несколько таких проходов — и шеренга выстроена.
Так работает сортировка пузырьком — самый простой алгоритм сортировки. Большие элементы постепенно «всплывают» в конец массива, как пузырьки воздуха в воде.
Идея алгоритма
Идем по массиву слева направо и сравниваем соседние элементы a[j] и a[j + 1]. Если левый больше правого, меняем их местами. Это один проход. После первого прохода самый большой элемент стоит в конце, после второго на свое место встает второй по величине, и так далее. Для массива из $n$ элементов хватает $n - 1$ проходов: когда на местах все, кроме одного, этот последний тоже стоит правильно.
Ключевая идея: После $k$-го прохода последние $k$ элементов уже стоят на своих местах. Поэтому каждый следующий проход можно делать на одно сравнение короче.
Разбор на примере
Отсортируем массив [4, 2, 5, 1, 3]. Первый проход подробно:
- 4 > 2 — меняем:
[2, 4, 5, 1, 3]. - 4 < 5 — оставляем.
- 5 > 1 — меняем:
[2, 4, 1, 5, 3]. - 5 > 3 — меняем:
[2, 4, 1, 3, 5]. Пятерка «всплыла» в конец.
Остальные проходы устроены так же, только каждый на одно сравнение короче:
| Проход | Сравнений | Обменов | Массив после прохода |
|---|---|---|---|
| 1 | 4 | 3 | [2, 4, 1, 3, 5] |
| 2 | 3 | 2 | [2, 1, 3, 4, 5] |
| 3 | 2 | 1 | [1, 2, 3, 4, 5] |
| 4 | 1 | 0 | [1, 2, 3, 4, 5] |
После третьего прохода массив уже отсортирован, и в четвертом не случилось ни одного обмена. Отсюда полезное улучшение: если за проход не было обменов, массив упорядочен, и дальше можно не проверять. Для почти отсортированного массива, например [1, 2, 4, 3, 5], хватит двух проходов вместо четырех: первый поменяет 4 и 3, второй убедится, что все на местах.
Реализация
Переменная swapped запоминает, был ли обмен за проход. Внутренний цикл идет до n - 1 - i: последние i элементов уже на местах.
def bubble_sort(a):
n = len(a)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j] # меняем соседей местами
swapped = True
if not swapped: # обменов не было - массив отсортирован
break
nums = [4, 2, 5, 1, 3]
bubble_sort(nums)
print(nums) # [1, 2, 3, 4, 5]
На C++ для обмена есть готовая функция swap:
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
void bubbleSort(vector<int>& a) {
int n = a.size();
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
swapped = true;
}
}
if (!swapped) break;
}
}
int main() {
vector<int> a = {4, 2, 5, 1, 3};
bubbleSort(a);
for (int x : a) cout << x << " "; // 1 2 3 4 5
cout << "\n";
}
Сложность
Хуже всего, когда массив отсортирован в обратном порядке: каждое сравнение заканчивается обменом, и ранний выход не срабатывает. Сравнений будет
Это $O(n^2)$: для 1000 элементов — 499 500 сравнений. Лучший случай — массив уже отсортирован: хватит одного прохода из $n - 1$ сравнений, то есть $O(n)$. Дополнительной памяти почти не нужно, только переменная для обмена — $O(1)$.
| Массив | Сравнений | Обменов | Сложность |
|---|---|---|---|
| Уже отсортирован | $n - 1$ | 0 | $O(n)$ |
| Случайный порядок | до $\frac{n(n - 1)}{2}$ | в среднем $\frac{n(n - 1)}{4}$ | $O(n^2)$ |
| Отсортирован наоборот | $\frac{n(n - 1)}{2}$ | $\frac{n(n - 1)}{2}$ | $O(n^2)$ |
Пузырек — учебный алгоритм. В настоящих программах сортируют встроенными средствами: sorted(a) или a.sort() в Python и sort(a.begin(), a.end()) в C++. Они работают за $O(n \log n)$ и на миллионе чисел делают в десятки тысяч раз меньше операций, чем пузырек.
Частая ошибка: Внутренний цикл до
nвместоn - 1 - i. На последнем шагеa[j + 1]выходит за конец массива: Python выдаст ошибкуIndexError, а C++ может молча прочитать чужую память и выдать мусор. Еще одна ловушка — сравнение>=вместо>: равные элементы начнут меняться местами впустую.
Проверь себя
Где окажется самый большой элемент массива после первого прохода сортировки пузырьком?
Сколько обменов сделает сортировка пузырьком, чтобы упорядочить массив [4, 1, 3, 2]?
Соедини характеристику сортировки пузырьком и ее значение.
Сложность в худшем случае
$O(n)$
Сложность на уже отсортированном массиве
$O(1)$
Дополнительная память
10
Сравнений в худшем случае при $n = 5$
$O(n^2)$