Сортировка клоуна Бозо :: BozoSort

Bozo the Clown
Одна из самых медленных сортировок. Практической пользы никакой, однако представляет теоретический интерес как крайне неэффективный алгоритм, использующий теорию вероятностей.

Способ назван в честь знаменитого детского клоуна потому, что его легко объяснить даже трёхлетнему ребёнку.

Сортировка клоуна Бозо

Алгоритм

Наугад выбираются и меняются местами два элемента. После этого проверяется, отсортирован ли массив. Если нет, то повторяются те же действия.

BozoSort — это «улучшенный» BogoSort.

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

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

Ссылки

Хабрахабр: Непрактичные сортировки – бессмысленные и беспощадные

Bozo the Clown on Wikipedia

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