Пузырьковая сортировка
Один из самых простых для понимания алгоритмов сортировки, полезен для обучения, но редко используется на практике из-за низкой эффективности.
Идея алгоритма
Массив многократно просматривается слева направо. На каждом проходе соседние элементы сравниваются и при необходимости меняются местами. Крупные элементы как бы «всплывают» к концу массива, как пузырьки.
Асимптотика:
- Время (худший / средний случай): O(n²)
- Время (лучший случай — массив уже отсортирован): O(n)
- Память: O(1) — сортировка «на месте»
- Стабильный алгоритм: порядок равных элементов сохраняется
Когда использовать
- Для обучения базовым идеям сортировок
- Для очень небольших массивов, где простота важнее скорости
- Когда нужна стабильная сортировка и важна понятность кода
Плюсы
- Очень прост для понимания и реализации;
- Не требует дополнительной памяти;
- Подходит, чтобы «почувствовать» работу сортировок.
Минусы
- Очень медленный на реальных данных;
- Даже при небольшом числе элементов делает много лишних операций;
- На практике почти всегда есть алгоритм лучше.
Пример кода
function bubbleSort(arr) {
const a = [...arr]; // копируем, чтобы не портить исходный массив
const n = a.length;
for (let i = 0; i < n - 1; i++) {
// каждый проход "всплывает" максимум в конец
for (let j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
[a[j], a[j + 1]] = [a[j + 1], a[j]];
}
}
}
return a;
}Попробуй самостоятельно написать алгоритм, а затем сравнить
Полезные темы
Рекомендуем изучить эти темы для лучшего понимания