Сортировка массива с минимальным количеством сравнений
Я нуждаюсь в некоторой помощи со своей домашней работой CS. Я должен записать программу сортировки, которая сортирует массив длины 5 использований 7 сравнений в худшем случае (я доказал, что 7 будет необходим, из-за высоты дерева решений).
Я рассмотрел использование 'трудно кодированного' дерева решений, но это означает, что алгоритм является действительно сложной и подсказала моя обучающая программа, это не способ, которым это, как предполагается, сделано.
Я проверил quicksort, сортировку слиянием, пирамидальную сортировку, d-ary пирамидальная сортировка, вид вставки, вид выбора, все не отвечают на требование, которое приводит меня полагать, что существует потребность в определенном алгоритме для массивов длины 5.
Действительно хотел бы получить некоторые подсказки к правильному направлению.
5 ответов
Да, в томе Кнута 3 стр. 185 (раздел 5.3.1). Впервые это было задокументировано в докторской диссертации, так что Ваш профессор очень строг к Вам! Не существует простого элегантного метода, Вы должны проследить его как частично упорядоченное дерево.
Вот он в листе. Протестировано OK (SBCL под Linux)
(defun small-sort (a)
"Sort a vector A of length 5"
(if (> (aref a 0) (aref a 1))
(rotatef (aref a 0) (aref a 1)))
(if (> (aref a 2) (aref a 3))
(rotatef (aref a 2) (aref a 3)))
(if (> (aref a 0) (aref a 2))
(progn
(rotatef (aref a 0) (aref a 2))
(rotatef (aref a 1) (aref a 3))))
(if (> (aref a 4) (aref a 2))
(if (> (aref a 4) (aref a 3))
(progn)
(rotatef (aref a 3) (aref a 4)))
(if (> (aref a 4) (aref a 0))
(rotatef (aref a 2) (aref a 4) (aref a 3))
(rotatef (aref a 0) (aref a 4) (aref a 3) (aref a 2))))
(if (> (aref a 1) (aref a 3))
(if (> (aref a 1) (aref a 4))
(rotatef (aref a 1) (aref a 2) (aref a 3) (aref a 4))
(rotatef (aref a 1) (aref a 2) (aref a 3)))
(if (> (aref a 1) (aref a 2))
(rotatef (aref a 1) (aref a 2))
(progn)))
a)
(defun check-sorted (a)
(do ((i 0 (1+ i)))
((>= i (1- (array-dimension a 0))))
;;(format t "~S ~S~%" (aref a i) (aref a (+ 1 i)))
(assert (<= (aref a i) (aref a (+ 1 i))))))
(defun rr ()
(dotimes (i 100000)
(let ((a (make-array 5 :initial-contents (list (random 1.0) (random 1.0) (random 1.0) (random 1.0) (random 1.0) ))))
;;(format t "A=~S~%" a)
(let ((res (small-sort a)))
(check-sorted res)
;;(format t "Res=~S~%" res)
))))
7 похоже, что это тоже может быть оболочка сортировка.
Дональд Кнут Искусство компьютерного программирования , том 3 имеет раздел именно по этой теме. У меня с собой нет книг, но я почти уверен, что Кнут представляет алгоритм для 5 элементов. Как вы подозреваете, не существует общего алгоритма, который дает минимальное количество сравнений для многих размеров, но есть ряд общих приемов, которые используются в таких алгоритмах.
Из смутных воспоминаний я восстановил алгоритм для 5 элементов, и это можно сделать за 7 сравнений. Сначала возьмите две отдельные пары, сравните их внутри и сравните меньшие пары каждой пары. Затем сравните оставшийся с большим из них. Теперь это делится на два случая в зависимости от того, был ли оставшийся элемент меньше или больше, но во всех случаях это ' Можно закончить на трех доступных сравнениях.
Я рекомендую рисовать картинки, чтобы помочь вам. Фотографии Кнута выглядят примерно так:
o---o / o---o
, где показаны результаты после первых трех сравнений (и, насколько я помню, такие изображения появляются во многих типах минимального сравнения). Линия соединяет два элемента, порядок которых нам известен. Наличие таких изображений помогает вам определить, с какими элементами сравнивать, поскольку вы хотите провести сравнение, которое даст вам максимальный объем информации.
Приложение: Поскольку есть принятый ответ с реальным кодом, я думаю, что нет никакого вреда в завершение этих диаграмм, и они могут быть полезным дополнением к ответу. Итак, начните с приведенного выше и сравните недостающий элемент с тем, что находится вверху слева. Если он больше, это приведет к
/--o
o
/ \--o
o
\--o
Теперь, сравните два больших элемента вверху справа, и мы получим
o---o---o / o---o
Теперь, сравнивая нижний правый элемент сначала со средним верхним, а затем с той стороной, к которой он принадлежит, мы правильно размещаем его, используя оставшиеся два сравнения .
Если первоначальное сравнение привело к тому, что оставшийся элемент был меньше, диаграмма принимает вид
o---o---o
/
o---o
Теперь сравним два, у которых еще нет ничего меньшего, чем они. Один из вариантов - это последняя диаграмма выше, которую можно решить с помощью оставшихся двух сравнений. Другой случай -
o---o
/
o---o---o
И здесь снова тот, который еще не находится в последовательности с другими, может быть правильно размещен с помощью двух сравнений.
мы размещаем его правильно, используя оставшиеся два сравнения.Если первоначальное сравнение привело к тому, что оставшийся элемент был меньше, диаграмма принимает вид
o---o---o
/
o---o
Теперь сравните два, у которых еще нет ничего меньшего, чем они. Один из вариантов - это последняя диаграмма выше, которую можно решить с помощью оставшихся двух сравнений. Другой случай -
o---o
/
o---o---o
И здесь снова тот, который еще не находится в последовательности с другими, может быть правильно размещен с помощью двух сравнений.
мы размещаем его правильно, используя оставшиеся два сравнения.Если первоначальное сравнение привело к тому, что оставшийся элемент был меньше, диаграмма принимает вид
o---o---o
/
o---o
Теперь сравните два, у которых еще нет ничего меньшего, чем они. Один из вариантов - это последняя диаграмма выше, которую можно решить с помощью оставшихся двух сравнений. Другой случай -
o---o
/
o---o---o
И здесь снова тот, который еще не находится в последовательности с другими, может быть правильно размещен с помощью двух сравнений.
Я не думаю, что жестко запрограммированное решение должно быть настолько сложным:
- Сравните (элементы) 2 и 3, и поменяйте местами, если необходимо
- Сравните 3 и 4, и поменяйте местами, если требуется
- Сравните 1 и 3, если 1 меньше, затем сравните 1 и 2, в противном случае сравните 1 и 4. Поместите 1 в правильный слот.
- ] Повторите шаг 3, за исключением элементов 3 и 5.
Это всегда будет использовать 7 сравнений.
РЕДАКТИРОВАТЬ:
Я не думаю, что это сработает: Шаг 4 нарушен, и может потребоваться 8-е сравнение. Рассмотрим:
Index | 1 | 2 | 3 | 4 | 5 |
Value | 2 | 3 | 4 | 5 | 1 |
Шаг 4:
- Сравните 3 и 5 == 4 против 1 == элемент 5 меньше, чем элемент 3
- Сравните 2 и 5 == 3 против 1 == элемент 5 меньше, чем элемент 2
- ??? Необходимо сравнить 1 и 5, чтобы узнать, куда поместить элемент 5.