使用最少的比较对数组进行排序

Question

我的CS作业需要一些帮助.我需要编写一个排序例程,在最坏的情况下使用7次比较对长度为5的数组进行排序(我已经证明,由于决策树的高度,需要7个).

我考虑使用决策树"硬编码",但这意味着算法非常复杂,并且我的导师暗示这不是它应该完成的方式.

我检查了快速排序,合并排序,堆排序,d-ary堆排序,插入排序,选择排序,都没有回答要求,这让我相信需要一个长度为5的数组的特定算法.

真的想得到正确方向的一些提示.

Answer 1

唐纳德克努特的"计算机编程艺术"第3卷有一个关​​于这个主题的部分.我没有这里的书,但我很确定Knuth提出了5个元素的算法.正如您所怀疑的那样,没有一种通用算法能够为许多大小提供最小数量的比较,但是在这种算法中使用了许多常用技巧.

从模糊的回忆中,我重建了5个元素的算法,它可以在7个比较中完成.首先,取两个单独的对,在其中进行比较,并比较每对中较小的一对.然后,将剩余的一个与其中较大的一个进行比较.现在根据剩余元素是小还是大来分成两种情况,但在所有情况下都可以在仍然可用的三种比较中完成.

我建议您绘制图片来帮助您.Knuth的照片是这样的:

   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

是的,这是在Knuth第3卷第185页(第5.3.1节).这是首次在博士论文中记录,所以你的教授对你很难!没有真正简单优雅的方法; 你必须将它作为部分有序的树来跟踪.

这是在lisp.测试好了(Linux上的SBCL)

(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)  
        ))))