WikiSort.ru - Не сортированное

Алгори́тм Нарайа́ны — нерекурсивный алгоритм, генерирующий по данной перестановке следующую за ней перестановку (в лексикографическом порядке). Придуман индийским математиком Пандитом Нарайаной^[en] в XIV веке.

Если алгоритм Нарайаны применить в цикле к исходной последовательности из ${\displaystyle n}$ элементов ${\displaystyle a_{1},a_{2},...,a_{n}}$ , упорядоченных так, что ${\displaystyle a_{1}\leqslant a_{2}\leqslant ...\leqslant a_{n}}$ , то он сгенерирует все перестановки элементов множества ${\displaystyle \{a_{1},a_{2},...,a_{n}\}}$ в лексикографическом порядке.

Другой особенностью алгоритма является то, что необходимо запоминать только один элемент перестановки.

Алгоритм

• Шаг 1: найти такой наибольший ${\displaystyle j}$ , для которого ${\displaystyle a_{j}<a_{j+1}}$ .
• Шаг 2: увеличить ${\displaystyle a_{j}}$ . Для этого надо найти наибольшее ${\displaystyle l>j}$ , для которого ${\displaystyle a_{l}>a_{j}}$ . Затем поменять местами ${\displaystyle a_{j}}$ и ${\displaystyle a_{l}}$ .
• Шаг 3: записать последовательность ${\displaystyle a_{j+1},...,a_{n}}$ в обратном порядке.

Оценка сложности

В случае перестановки, где элементы перемешаны случайным образом, сложность алгоритма практически не зависит от количества элементов. В приведённых выше реализациях производится в среднем 3 сравнения элементов перестановки и 2.17 обменов.

Наилучшим является случай, когда предпоследний элемент перестановки больше последнего, тогда производится 2 сравнения и 1 обмен. Худшим является случай, когда элементы перестановки отсортированы по убыванию, и, если длина перестановки равна n, то производится n+1 сравнений и n/2+1 обменов.

В целом сложность алгоритма можно оценить как O(n).

Литература

Имеется викиучебник по теме
«Алгоритм Нарайаны»

• Knuth, D. E. The Art of Computer Programming. — Addison-Wesley, 2005. — Vol. 4. — ISBN 0-201-85393-0.

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 17 января 2015 года.

Для улучшения этой статьи желательно: Викифицировать статью.