Алгоритм сортировки которая делает наименьшее количество перестановок

#cpp #алгоритм #сортировка

Алгоритм сортировки которая делает наименьшее количество перестановок. 
Есть ли такой алгоритм и как реализовать его и вывести количество перестановок.Помогите
плиз ? Не знаю такого алгоритма.
    

Ответы

Ответ 1

Если речь идет об разнообразных алгоритмах обменных in-place сортировок, то минимальное
количество перестановок пар (обменов) элементов достигается на обыкновенной классической
Сортировке Выбором. Она сразу перемещает очередной элемент в его финальную позицию,
т.е. делает не более N-1 обменов.

Если же требуется минимизировать количество модификаций элементов исходного массива
(записей в исходный массив), то эта величина минимизируется Циклической Сортировкой,
которая просто в лоб вычисляет финальную позицию каждого элемента массива (путем подсчета
количества меньших элементов) и сразу переносит элемент в его финальное положение ("вытесняя"
оттуда хранящийся там элемент), после чего выполняет ту же операцию для вытесненного
элемента и т.д. тем самым выполняя обход цикла перестановки до возврата в начало цикла.
Обойдя все циклы, вы полностью отсортируете массив, выполнив не более N записей в него.


Ответ 2

Совершенно некорректно поставленный вопрос, просто потому, что вы спрашиваете только
о перестановках. Тогда годится, например, немного модифицированный алгоритм сортировки
выбором - он будет работать медленно, но перестановок будет ровно столько, сколько
надо, чтоб поставить все элементы на свои места.

Например, находим позиции элементов в отсортированной последовательности, ничего
не переставляя - скажем, выделив для этого еще один массив, а затем сразу ставим каждый
элемент на свое место, при возможности обменивая с тем, который при этом тоже станет
на свое место. Вы же ничего не спрашиваете о том, каковы допустимые затраты на дополнительную
память или количество сравнений?

Формально алгоритм выбором выполняет перестановок точно не больше, чем общее количество
элементов, но при этом его время работы - O(N2).

Или вас реально интересует именно количество перестановок?


Ответ 3

вобще многое зависит от того что сортируется, если числа то существует сортировка
подсчётом

она вобще ни одного обмена не делает, и в лучшем случае работает за линейное время.