Богосорт
-
Основы богосорта
- Богосорт — это алгоритм сортировки, основанный на генерации и тестировании перестановок.
- Он не считается эффективным для сортировки, но используется в образовательных целях.
-
Версии богосорта
- Существует детерминированная и рандомизированная версии богосорта.
- Рандомизированная версия имитирует сортировку колоды карт, подбрасывая их в воздух.
- В худшем случае рандомизированная версия может не найти отсортированную перестановку из-за низкого качества случайного источника.
-
Описание алгоритма
- Псевдокод для рандомизированной версии богосорта представлен в статье.
- Реализация на языке программирования C и Python также приведена.
-
Время выполнения и завершение
- В среднем случае количество сравнений и перестановок растет с увеличением размера коллекции.
- В лучшем случае, когда список уже отсортирован, количество сравнений равно количеству элементов минус один.
- Для любой коллекции фиксированного размера время работы алгоритма конечно.
-
Связанные алгоритмы и рекомендации
- Статья упоминает другие алгоритмы сортировки, такие как алгоритм Лас-Вегаса и что-то вроде марионетки.
- Ссылки на внешние ресурсы, включая Википедию и реализацию на C++, также предоставлены.