Сортировка массива с минимальным количеством сравнений

Мне нужна помощь в моей домашней домашней работе. Мне нужно написать процедуру сортировки, которая сортирует массив длиной 5, используя 7 сравнений в худшем случае (я доказал, что 7 будет необходимо из-за высоты дерева решений).

Я считал использование дерева решений "жестко закодированным", но это означает, что алгоритм действительно сложный, и мой учитель намекнул, что он не так, как это должно быть сделано.

Я проверил quicksort, сортировку слияния, сортировку кучи, сортировку кучи d-ary, сортировку вставки, сортировку сортировки, все не отвечают требованию, что заставляет меня полагать, что нужен конкретный алгоритм для массивов длины 5.

Очень хотелось бы получить подсказки в правильном направлении.

Ответ 1

Да, это в Knuth vol 3 стр. 185 (раздел 5.3.1). Это было впервые задокументировано в кандидатской диссертации, так что ваш Профессор довольно тяжелый для вас! Существует не очень простой элегантный метод; вы должны отслеживать его как частично упорядоченное дерево.

Здесь он находится в lisp. Протестировано ОК (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)  
        ))))

Ответ 2

Дональд Кнут Искусство компьютерного программирования, том 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

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

Ответ 3

7 звучит так, как будто это может быть shell также сортировать.

Ответ 4

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

Сравнить (элементы) 2 и 3 и поменять местами при необходимости
Сравните 3 и 4 и замените, если требуется
Сравните 1 и 3, если 1 меньше, затем сравните 1 и 2, в противном случае сравните 1 и 4. Поместите 1 в правильный слот.
Повторите шаг 3, за исключением элементов 3 и 5.

Это всегда будет использовать 7 сравнений.

EDIT:

Я не думаю, что это сработает: шаг 4 сломан и может потребовать 8-го сравнения. Рассмотрим:

Index | 1 | 2 | 3 | 4 | 5 |
Value | 2 | 3 | 4 | 5 | 1 |

Шаг 4:

Сравнить 3 и 5 == 4 vs 1 == элемент 5 меньше элемента 3
Сравнить 2 и 5 == 3 vs 1 == элемент 5 меньше элемента 2
??? Вам нужно сравнить 1 и 5, чтобы узнать, куда поместить элемент 5.

Ответ 5

Сортировка веток может быть реализована как алгоритм сравнения следующим образом:

Возьмите элемент.

Сравните его со всеми ведрами.

Поместите его в ведро, которое соответствует. < - Необходимое сравнение.

Если ведро не найдено, создайте новое ведро.

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

Я уже изобрел/описал это в новостной группе в прошлом.

Ответ 6

Посмотрите на сортировку ковша.