Пузырьковая сортировка :: Bubble sort
Одна из самых простейших сортировок. Не применяется для решения практических задач, ввиду низкой эффективности. Быстро упорядочивает только массивы очень небольшого размера.С другой стороны, метод используется в учебных целях, поскольку лежит в основе некоторых других сортировок, более эффективных.
Алгоритм
Осуществляется многократный прогон по массиву - сначала от первого до последнего элемента, потом от первого до предпоследнего, потом от первого до третьего с конца и т.д. При прогоне сравниваются соседние элементы. Если они не упорядочены относительно друг друга, то меняются местами. В результате при каждом прогоне в конец текущего подмассива всплывает наибольший (наименьший) элемент.
Небольшая оптимизация позволяет экономить на проходах по началу массива при каждой итерации.
Модификации
"Пузырёк" - это улучшенная глупая сортировка. В глупой сортировке при обмене неотсортированных соседей происходит возврат в начало массива. Здесь же просмотр продолжается далее.Сама пузырьковая сортировка является отправной точкой для некоторых других обменных алгоритмов:
- Коктейльная сортировка. Двунаправленная пузырьковая сортировка, попеременно крупные элементы вытесняются в конец массива, а небольшие по значению - в начало.
- Чётно-нечётная сортировка. За один проход нечётные индексы сравниваются с чётными, затем чётные - с нечётными.
- Сортировка расчёской. Сравниваются не соседи, а элементы между которыми некоторое расстояние, уменьшающееся с каждым прогоном по массиву.
Характеристики алгоритма
| Название | Пузырьковая сортировка (Bubble sort) | |
|---|---|---|
| Другие названия | Сортировка простыми обменами | |
| Класс | Сортировки обменами | |
| Устойчивость | Да | |
| Сравнения | Да | |
| Сложность по времени | Худшая | O(n2) |
| Средняя | O(n2) | |
| Лучшая | O(n) | |
| Сложность по памяти | Общая | O(n) |
| Дополнительная | O(1) | |
Пузьрьковая сортировка
Реализация на различных ЯП