Bubble Sort
Bubble Sort — простой алгоритм сортировки, который сравнивает соседние элементы и меняет их местами.
Основная идея
На каждом проходе самый большой элемент "всплывает" в конец массива.
Пошаговый пример
Исходный массив:
[5, 3, 8, 4, 2]- 5 и 3 → меняем → [3, 5, 8, 4, 2]
- 8 и 4 → меняем → [3, 5, 4, 8, 2]
- 8 и 2 → меняем → [3, 5, 4, 2, 8]
- Дальше повторяем проходы, пока не получим [2, 3, 4, 5, 8]
Псевдокод
for i from 0 to n - 1:
swapped = false
for j from 0 to n - i - 2:
if arr[j] > arr[j + 1]:
swap(arr[j], arr[j + 1])
swapped = true
if not swapped:
break
Оптимизация: Используйте флаг swapped, чтобы завершать алгоритм раньше, если массив уже отсортирован.
Сложность
Время
O(n²) в среднем и худшем случае, O(n) в лучшем (с оптимизацией).
Память
O(1), сортировка in-place.
Когда используется
- Обучение
- Очень маленькие массивы
- Прототипирование
Ключевые свойства
- Стабильный
- In-place
- Простой, но медленный