Визуализация
Данные: Случайные
Легенда цветов
Как работает сортировка пузырьком
Идея алгоритма. Проходим по массиву слева направо и сравниваем каждую пару соседних элементов. Если левый больше правого - меняем их местами. За один такой проход наибольший элемент гарантированно доезжает до конца массива, как пузырек воздуха всплывает на поверхность воды. Отсюда и название.
Почему хвост зеленеет. После первого прохода последний элемент стоит на своем месте, после второго - два последних, и так далее. Поэтому каждый следующий проход короче предыдущего: проверять зеленую зону уже не нужно.
Умная остановка. Если за целый проход не случилось ни одного обмена, значит массив уже отсортирован и можно останавливаться. Благодаря этой оптимизации на уже отсортированных данных алгоритм делает всего один проход - попробуйте набор "Отсортированные" и сравните число операций с набором "В обратном порядке".
- Случайные - обычный средний случай, примерно n²/4 обменов.
- В обратном порядке - худший случай: меняется каждая пара.
- Отсортированные - лучший случай: один проход и ноль обменов.
- Почти отсортированные - несколько "выбитых" элементов быстро встают на место.
- Одинаковые - сравнения идут, а обменов нет ни одного.
Синонимы названия. Этот алгоритм также известен как сортировка простым обменом (официальное академическое название), сортировка обменами (exchange sort) и сортировка погружением (sinking sort).
Сложность алгоритма
Сложность - это оценка того, как быстро растет потребление ресурса при росте длины массива n. Ресурса у алгоритма два, поэтому и оценки две: по времени и по памяти. Обе записывают через O-нотацию - у нас есть отдельная анимация о том, как читать такие записи.
По времени
Показывает, как растет число операций (здесь это сравнения и обмены) при росте n. Лейбл "Сложность" под визуализацией - время, которое получилось фактически на ваших данных.
| Случай | Время | Комментарий |
|---|---|---|
| Лучший (массив отсортирован) | O(n) | Один проход без обменов - и умная остановка |
| Средний | O(n²) | Число сравнений растет квадратично |
| Худший (обратный порядок) | O(n²) | Обмен на каждом сравнении |
По памяти
Показывает, сколько дополнительной памяти нужно алгоритму. Сам входной массив в эту оценку не входит: дополнительной считается память сверх него.
| Характеристика | Оценка | Комментарий |
|---|---|---|
| Дополнительная память | O(1) | Сортировка на месте: хватает одной временной переменной для обмена, сколько бы элементов ни было |
Устойчивость алгоритма
Устойчивой называется сортировка, которая не меняет взаимный порядок равных элементов. Пример: сортируем учеников по оценке, а внутри одной оценки они уже стояли по алфавиту. Устойчивая сортировка сохранит алфавитный порядок внутри каждой оценки, неустойчивая - может перемешать.
| Характеристика | Оценка | Комментарий |
|---|---|---|
| Устойчивость | Да | Обмен только при строгом "больше": равные элементы не перепрыгивают друг через друга. Проверьте на наборе "Одинаковые" - обменов не будет вовсе |
Примеры реализации сортировки пузырьком (Bubble Sort)
Код на C
void bubble_sort(int arr[], int n) {
// Проходим по всему массиву
for (int i = 0; i < n - 1; i++) {
int swapped = 0;
// Внутренний цикл идет только до неотсортированной части
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// Меняем элементы местами
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
// Остановка, если обменов не было
if (!swapped) {
break;
}
}
}Код на Python
def bubble_sort(arr):
n = len(arr)
# Проходим по всему массиву
for i in range(n - 1):
swapped = False
# Внутренний цикл идет только до неотсортированной части
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
# Меняем элементы местами, если они стоят неправильно
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# Если за весь проход обменов не было - массив отсортирован
if not swapped:
break
return arrКод на JavaScript
function bubbleSort(arr) {
const n = arr.length;
// Проходим по всему массиву
for (let i = 0; i < n - 1; i++) {
let swapped = false;
// Внутренний цикл идет только до неотсортированной части
for (let j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// Меняем элементы местами
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// Остановка, если обменов не было
if (!swapped) {
break;
}
}
return arr;
}Хотите разобрать тему глубже? В нашем бесплатном курсе есть урок про пузырьковые сортировки - с подробной теорией, задачами и проверочными вопросами.