Алгоритм сортировки которая делает наименьшее количество перестановок. Есть ли такой алгоритм и как реализовать его и вывести количество перестановок.Помогите плиз ? Не знаю такого алгоритма.
-
что имеется ввиду под перестановками ? обмены не равных элементов ?– ampawdCommented 29 апр. 2017 в 19:47
-
на отсортированной коллекции любой алгоритм сделает 0 перестановок– Grundy ♦Commented 29 апр. 2017 в 19:48
-
2@Grundy не любой а только устойчивый алгоритм - так как если в отсортированной последовательности некоторые элементы равны в неустойчивом алгоритме они обменяются местами– ampawdCommented 29 апр. 2017 в 19:50
-
@ampawd, разве?– Grundy ♦Commented 29 апр. 2017 в 19:51
-
1@futuretourist: О чем речь вообще? Что такое "пометить" и откуда какое-то "помечание" вообще взялось в этой задаче?– AnT stands with RussiaCommented 30 апр. 2017 в 4:15
3 ответа
Если речь идет об разнообразных алгоритмах обменных in-place сортировок, то минимальное количество перестановок пар (обменов) элементов достигается на обыкновенной классической Сортировке Выбором. Она сразу перемещает очередной элемент в его финальную позицию, т.е. делает не более N-1 обменов.
Если же требуется минимизировать количество модификаций элементов исходного массива (записей в исходный массив), то эта величина минимизируется Циклической Сортировкой, которая просто в лоб вычисляет финальную позицию каждого элемента массива (путем подсчета количества меньших элементов) и сразу переносит элемент в его финальное положение ("вытесняя" оттуда хранящийся там элемент), после чего выполняет ту же операцию для вытесненного элемента и т.д. тем самым выполняя обход цикла перестановки до возврата в начало цикла. Обойдя все циклы, вы полностью отсортируете массив, выполнив не более N записей в него.
-
1Но если только первый элемент не на своем месте, то будет сделано n-1 перестановок. Тут нужна модификация, которая найдет максимальный упорядоченный набор и досортирует к нему остальные элементы.– megaCommented 30 апр. 2017 в 7:16
-
1@mega: Как может быть не на своем месте только один элемент??? Это невозможно. Напоминаю, что я веду речь о классических in-place сортировках. Commented 30 апр. 2017 в 7:25
-
1Не, in-place тут ни при чем, отсортируйте вставками массив 5,1,2,3,4. Вы тут переставите все элементы, хотя достаточно только один. Это классическая проблема.– megaCommented 30 апр. 2017 в 21:06
-
@mega: Это как это вы предлагаете отсортировать массив { 5,1,2,3,4 }, переставив только один элемент??? Commented 30 апр. 2017 в 21:15
-
Совершенно некорректно поставленный вопрос, просто потому, что вы спрашиваете только о перестановках. Тогда годится, например, немного модифицированный алгоритм сортировки выбором - он будет работать медленно, но перестановок будет ровно столько, сколько надо, чтоб поставить все элементы на свои места.
Например, находим позиции элементов в отсортированной последовательности, ничего не переставляя - скажем, выделив для этого еще один массив, а затем сразу ставим каждый элемент на свое место, при возможности обменивая с тем, который при этом тоже станет на свое место. Вы же ничего не спрашиваете о том, каковы допустимые затраты на дополнительную память или количество сравнений?
Формально алгоритм выбором выполняет перестановок точно не больше, чем общее количество элементов, но при этом его время работы - O(N2).
Или вас реально интересует именно количество перестановок?
вобще многое зависит от того что сортируется, если числа то существует сортировка подсчётом
она вобще ни одного обмена не делает, и в лучшем случае работает за линейное время.
-
1в худшем тоже) Только вот линейно не от числа элементов, а от размера "корзины".– pavelCommented 29 апр. 2017 в 19:54
-
@pavel сложность тут ещё и от реализации этого алгоритма зависит– ampawdCommented 29 апр. 2017 в 19:55
-
Каким образом вы предлагаете применять этот алгоритм в общем случае, если элементы исходного массива - не числа? Commented 30 апр. 2017 в 4:06
-
@AnT я такое не предлагал вобще то )) но вопрос этот конечно интересный– ampawdCommented 30 апр. 2017 в 9:38