Сортировка перестановками :: PermSort

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

Сортировка перестановками

Алгоритм

Если подойти к сортировке как к комбинаторной задаче, то массив можно рассматривать как обычное конечное множество из n элементов, для которого существует n! перестановок. Некоторые из этих перестановок – массив в упорядоченном состоянии. Перебираем все возможные перестановки, пока не встретим ту, которая представляет из себя отсортированный массив.

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

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

Ссылки

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

Реализация на различных ЯП

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