Сортировка клоуна Бозо :: BozoSort
Одна из самых медленных сортировок. Практической пользы никакой, однако представляет теоретический интерес как крайне неэффективный алгоритм, aиспользующий теорию вероятностей.Способ назван в честь знаменитого детского клоуна потому, что его легко объяснить даже трёхлетнему ребёнку.
Алгоритм
Наугад выбираются и меняются местами два элемента. После этого проверяется, отсортирован ли массив. Если нет, то повторяются те же действия.BozoSort - это "улучшенный" BogoSort.
Характеристики алгоритма
| Название | Сортировка клоуна Бозо (Bozo sort) | |
|---|---|---|
| Класс | Сортировки обменами | |
| Устойчивость | Нет | |
| Сравнения | Да | |
| Сложность по времени | Худшая | ∞ |
| Средняя | O(n x n!) | |
| Лучшая | O(n) | |
| Сложность по памяти | Общая | O(n) |
| Дополнительная | O(1) | |
Bozo the Clown