Пузырьковая сортировка :: Bubble sort

Пузырьковая сортировка

Одна из самых простейших сортировок. Не применяется для решения практических задач, ввиду низкой эффективности. Быстро упорядочивает только массивы очень небольшого размера.С другой стороны, метод используется в учебных целях, поскольку лежит в основе некоторых других сортировок, более эффективных.

Алгоритм

Осуществляется многократный прогон по массиву - сначала от первого до последнего элемента, потом от первого до предпоследнего, потом от первого до третьего с конца и т.д. При прогоне сравниваются соседние элементы. Если они не упорядочены относительно друг друга, то меняются местами. В результате при каждом прогоне в конец текущего подмассива всплывает наибольший (наименьший) элемент.

Небольшая оптимизация позволяет экономить на проходах по началу массива при каждой итерации.

Модификации

"Пузырёк" - это улучшенная глупая сортировка. В глупой сортировке при обмене неотсортированных соседей происходит возврат в начало массива. Здесь же просмотр продолжается далее.Сама пузырьковая сортировка является отправной точкой для некоторых других обменных алгоритмов:

Характеристики алгоритма

НазваниеПузырьковая сортировка (Bubble sort)
Другие названияСортировка простыми обменами
КлассСортировки обменами
УстойчивостьДа
СравненияДа
Сложность по времениХудшаяO(n2)
СредняяO(n2)
ЛучшаяO(n)
Сложность по памятиОбщаяO(n)
ДополнительнаяO(1)

Ссылки

Сортировки обменами

Пузырьковая сортировка и все-все-все

Пузьрьковая сортировка

Bubble sort

Реализация на различных ЯП