Сортировка чисел по алгоритму суммы

Как намек, это пахнет динамическим программированием; Возможно, это недостаточно точный намек, чтобы помочь, но я бы предпочел начать с малого!

Вы платите за количество свопов, а не за количество сравнений. Вы также не упомянули, что вас взимали за ведение других записей.

Сравнения и обходы, по-видимому, бесплатны, вы можете предварительно рассчитать «расстояние», которое должно пройти число (и, по сути, окончательный порядок сортировки). Загадка заключается в алгоритме обмена.

Очевидно, что минимизация общих свопов важна. Также важно минимизировать свопы больших чисел.

Я почти уверен, что оптимальный процесс подкачки не может быть гарантирован путем оценки каждого порядка без сохранения состояния, хотя вы часто можете приблизиться к нему (не проблема).

Я предполагаю, что память свободна, и вы можете смоделировать сортировку, прежде чем выполнять ее на реальных объектах.

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

Запустите цикл, который удаляет элемент очереди с наименьшей стоимостью и ставит в очередь все возможные шаги однократной замены, начиная с этой точки. Продолжайте запускать цикл, пока в заголовке очереди не появится отсортированный список.

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

Найдите наименьшее число N. Любые пары чисел, которые занимают желаемые места друг друга, должны быть заменены местами, кроме N. Соберите (грубой силой) коллекцию каждого набора чисел, которые можно взаимно поменять местами в нужные места, так, чтобы стоимость сортировки набора между собой была меньше, чем стоимость замены каждого элемента набора на N. Эти наборы будут состоять из нескольких циклов. Меняйте местами эти циклы таким образом, чтобы наименьшее число менялось местами дважды. Поменяйте местами все оставшиеся числа, которые составляют цикл, включающий N, используя N в качестве заполнителя.

Я сделал несколько попыток решить один из примеров вручную:

• 1 8 9 7 6
• 6 8 9 7 1 (+ 6 + 1 = 7)
• 6 8 1 7 9 (7 + 1 + 9 = 17)
• 6 8 7 1 9 (17 + 1 + 7 = 25)
• 6 1 7 8 9 (25 + 1 + 8 = 34)
• 1 6 7 8 9 (34 + 1 + 6 = 41)

Поскольку вам нужно было заменить 1, кажется, что вам, возможно, придется провести исчерпывающий поиск, чтобы решить проблему, детали которой уже были опубликованы другим пользователем. Обратите внимание, что при использовании этого метода вы столкнетесь с проблемами, если набор данных большой.

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

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

Например, 5,3,4,2,1 имеет два цикла: (5,1) и (3,4,2). Цикл можно представить как начало с 3, 4 находится в точке 3, 2 - в точке 4, а 4 - в точке 3. определять. Конечная цель - 1,2,3,4,5 или (1) (2) (3) (4) (5), пять непересекающихся циклов.

Если мы переключим два элемента из разных циклов, скажем 1 и 3, мы получим: 5,1,4,2,3 и в обозначении цикла (1,5,3,4,2). Два цикла объединены в один цикл, это противоположно тому, что мы хотим сделать.

Если мы переключим два элемента из одного цикла, скажем 3 и 4, мы получим: 5,4,3,2,1 в обозначении цикла (5,1) (2,4) (3). Один цикл делится на два меньших цикла. Это приближает нас к цели всех циклов длины 1. Обратите внимание, что любое переключение двух элементов в одном цикле разбивает цикл на два цикла.

Если мы сможем выяснить оптимальный алгоритм переключения одного цикла, мы сможем применить его ко всем циклам и получить оптимальный алгоритм для всей сортировки. Один из алгоритмов состоит в том, чтобы взять минимальный элемент в цикле и переключить его на то, в чьей позиции он находится. Итак, для (3,4,2) мы бы переключили 2 на 4. Это оставляет нам цикл длиной 1 ( элемент только что переключился в правильное положение) и цикл размером на единицу меньше, чем раньше. Затем мы можем снова применить правило. Этот алгоритм переключает наименьшую длину цикла элемента -1 раз и каждый другой элемент один раз.

Чтобы преобразовать цикл длины n в циклы длины 1, требуется n - 1 операция. С каждым элементом нужно работать хотя бы один раз (подумайте о каждом элементе, который нужно отсортировать, он должен быть перемещен в правильное положение). Предложенный мной алгоритм воздействует на каждый элемент один раз, что должны делать все алгоритмы, затем все остальные операции выполняются с минимальным элементом. Нет алгоритма лучше.

Этот алгоритм занимает O (n log n) для сортировки, а затем O (n), чтобы возиться с циклами. Решение одного цикла занимает O (длина цикла), общая длина всех циклов равна n, поэтому стоимость операций цикла составляет O (n). Конечное время выполнения - O (n log n).