Временная сложность
Лучший: O(n)
Средний: O(n²)
Худший: O(n²)
Bubble Sort — это простой алгоритм сортировки, основанный на сравнении элементов. Он многократно проходит по списку, сравнивает соседние элементы и меняет их местами, если они расположены в неправильном порядке.
Алгоритм получил своё название потому, что меньшие элементы постепенно «всплывают» в начало списка после каждого прохода.
Как это работает:
1. Сравнить каждую пару соседних элементов
2. Поменять их местами, если левый элемент больше правого
3. После каждого прохода наибольший из ещё не отсортированных элементов занимает свою окончательную позицию
4. Повторять процесс, пока обмены больше не требуются
Временная сложность:
Лучший случай: O(n) — список уже отсортирован
Средний случай: O(n²)
Худший случай: O(n²)
Пространственная сложность: O(1) — сортировка на месте
Свойства:
- Стабильная сортировка
- Адаптивный алгоритм
- Сортировка на месте
В основном используется в образовательных целях. Для production-систем предпочтительнее Quick Sort или Merge Sort.
Похожие алгоритмы
Частые вопросы
- Что такое Сортировка пузырьком (Bubble Sort)?
- Bubble Sort — это простой алгоритм сортировки, основанный на сравнении элементов. Он многократно проходит по списку, сравнивает соседние элементы и меняет их местами, если они расположены в неправильном порядке.
- Какова сложность Сортировка пузырьком (Bubble Sort)?
- Время (среднее): O(n²) · Память: O(1)
- Для кого предназначена визуализация Сортировка пузырьком (Bubble Sort)?
- Визуализация Сортировка пузырьком (Bubble Sort) рассчитана на начальный уровень в категории «Сортировка». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с Сортировка пузырьком (Bubble Sort)?
- В той же категории (Сортировка) вы можете изучить: Selection Sort, Insertion Sort, Quick Sort. Каждый из них имеет интерактивную визуализацию.