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

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

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

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

Алгоритм

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

Модификации

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

Сама пузырьковая сортировка является отправной точкой для некоторых других обменных алгоритмов:

  • Коктейльная сортировка. Двунаправленная пузырьковая сортировка, попеременно крупные элементы вытесняются в конец массива, а небольшие по значению — в начало.
  • Чётно-нечётная сортировка. За один проход нечётные индексы сравниваются с чётными, затем чётные — с нечётными.
  • Сортировка расчёской. Сравниваются не соседи, а элементы между которыми некоторое расстояние, уменьшающееся с каждым прогоном по массиву.

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

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

Ссылки

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

Пузьрьковая сортировка в Википедии
Bubble sort on Wikipedia
Реализация на различных ЯП

Добавить комментарий