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

一尘不染

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

algorithm

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

我考虑过使用决策树“硬编码”，但这意味着算法确实很复杂，并且由我的导师暗示这不是应该完成的方式。

我检查了quicksort，merge排序，heap排序，dary堆排序，insert排序，selection排序，所有这些都没有满足要求，这使我相信对于长度为5的数组需要一种特定的算法。

真的很想获得一些正确方向的提示。

阅读 230

2020-07-28

共1个答案

一尘不染

是的，它在Knuth第3卷第185页（第5.3.1节）中。这是第一次在博士论文中记录，因此您的教授对您很努力！没有真正简单的优雅方法。您必须将其作为部分排序的树进行跟踪。

在这里，它隐隐约约。经测试确定（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)  
        ))))

2020-07-28