Сортировка перестановками :: PermSort
Из числа крайне медленных сортировок. Не имеет практической пользы, однако представляет чисто академический интерес, как пример неэффективного алгоритма.
Алгоритм
Если подойти к сортировке как к комбинаторной задаче, то массив можно рассматривать как обычное конечное множество из n элементов, для которого существует n! перестановок. Некоторые из этих перестановок – массив в упорядоченном состоянии. Перебираем все возможные перестановки, пока не встретим ту, которая представляет из себя отсортированный массив.
Характеристики алгоритма
| Название | Сортировка перестановками (Perm sort, Permulation sort) | |
|---|---|---|
| Класс | Сортировки обменами | |
| Устойчивость | Неустойчивая | |
| Сравнения | Нет | |
| Сложность по времени | Худшая | O(n x n!) |
| Средняя | O(n x n!) | |
| Лучшая | O(n) | |
| Сложность по памяти | Общая | O(n) |
| Дополнительная | O(1) | |
Реализация на различных ЯП