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

Question

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

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

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

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

Answer 1

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

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

Answer 2

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

Вот оно в Лиспе. Протестировано нормально (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)  
        ))))  

Answer 3

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

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

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

Брось его в соответствующее ведро. <- Требуется сравнение. </p>

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

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

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

Answer 4

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

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

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

EDIT:

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

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

Шаг 4:

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

Answer 5

7 звучит так, как будто это shell sort.

Answer 6

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