4

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

14
  • что имеется ввиду под перестановками ? обмены не равных элементов ?
    – ampawd
    Commented 29 апр. 2017 в 19:47
  • на отсортированной коллекции любой алгоритм сделает 0 перестановок
    – Grundy
    Commented 29 апр. 2017 в 19:48
  • 2
    @Grundy не любой а только устойчивый алгоритм - так как если в отсортированной последовательности некоторые элементы равны в неустойчивом алгоритме они обменяются местами
    – ampawd
    Commented 29 апр. 2017 в 19:50
  • @ampawd, разве?
    – Grundy
    Commented 29 апр. 2017 в 19:51
  • 1
    @futuretourist: О чем речь вообще? Что такое "пометить" и откуда какое-то "помечание" вообще взялось в этой задаче? Commented 30 апр. 2017 в 4:15

3 ответа 3

5

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

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

8
  • 1
    Но если только первый элемент не на своем месте, то будет сделано n-1 перестановок. Тут нужна модификация, которая найдет максимальный упорядоченный набор и досортирует к нему остальные элементы.
    – mega
    Commented 30 апр. 2017 в 7:16
  • 1
    @mega: Как может быть не на своем месте только один элемент??? Это невозможно. Напоминаю, что я веду речь о классических in-place сортировках. Commented 30 апр. 2017 в 7:25
  • 1
    Не, in-place тут ни при чем, отсортируйте вставками массив 5,1,2,3,4. Вы тут переставите все элементы, хотя достаточно только один. Это классическая проблема.
    – mega
    Commented 30 апр. 2017 в 21:06
  • @mega: Это как это вы предлагаете отсортировать массив { 5,1,2,3,4 }, переставив только один элемент??? Commented 30 апр. 2017 в 21:15
  • ну вот так - 5 поставить в конец, удивил? )
    – mega
    Commented 30 апр. 2017 в 21:16
3

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

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

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

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

2

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

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

4
  • 1
    в худшем тоже) Только вот линейно не от числа элементов, а от размера "корзины".
    – pavel
    Commented 29 апр. 2017 в 19:54
  • @pavel сложность тут ещё и от реализации этого алгоритма зависит
    – ampawd
    Commented 29 апр. 2017 в 19:55
  • Каким образом вы предлагаете применять этот алгоритм в общем случае, если элементы исходного массива - не числа? Commented 30 апр. 2017 в 4:06
  • @AnT я такое не предлагал вобще то )) но вопрос этот конечно интересный
    – ampawd
    Commented 30 апр. 2017 в 9:38

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.