用最less的比较数sorting一个数组

我需要一些帮助,我的CS功课。 我需要编写一个sorting例程,在最差的情况下使用7个比较对一个长度为5的数组进行sorting(由于决策树的高度,我已经certificate需要7个)。

我考虑使用“硬编码”决策树,但这意味着algorithm非常复杂,我的导师暗示,这不是它应该做的方式。

我检查过快排,合并sorting,堆sorting,d堆sorting,插入sorting,selectsorting,都不回答要求,这导致我相信有一个长度为5的数组的特定algorithm的需要。

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

是的,它在Knuth第3卷第185页(第5.3.1节)。 这首先是在博士论文中logging的,所以你的教授对你很重要! 没有真正简单的优雅的方法; 您必须将其作为部分有序的树进行追踪。

这里是在lisp。 testing好(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 ai) (aref a (+ 1 i))) (assert (<= (aref ai) (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) )))) 

Donald Knuth的“计算机编程的艺术”第3卷有关于这个主题的一节。 我没有和我在一起的书,但是我非常肯定Knuth提出了5个元素的algorithm。 正如你所怀疑的那样,没有一个通用algorithm给出了许多尺寸的最小比较次数,但是在这样的algorithm中有很多常用的技巧。

从模糊的回忆中,我重build了5个元素的algorithm,可以在7个比较中完成。 首先,拿两个单独的对,在里面进行比较,然后比较每对中较小的一对。 然后,比较剩余的一个与这些更大的。 现在根据剩余的元素是小还是大来分为两种情况,但是在所有情况下,仍然有可能在三种比较中完成。

我build议画图来帮助你。 Knuth的照片是这样的:

    ØØ---
   /
  ØØ---

它显示了前三次比较后的结果(从我记得的情况来看,这种图片出现在许多最小比较种类中)。 一条线连接两个我们知道的顺序的元素。 有了这样的图片可以帮助你确定哪些元素进行比较,因为你想做一个比较,给你最大的信息量。

附录:由于实际代码有一个公认的答案,所以我认为完成这些图表没有什么坏处,它们可能是对答案的有益补充。 所以,从上面的一个开始,比较缺less的元素与左上angular的元素。 如果它更大,这将导致

     /  - Ø
    Ø
   / \  -  o
  Ø
   \  - Ø

现在,比较右上angular的两个大元素,我们结束了

    Ø -  O  -  O
   /
  ØØ---

现在,通过比较右下angular的元素与顶部的中间的元素,然后反对它所属的那一边,我们使用剩余的两个比较正确地放置它。

如果初始比较导致剩余元素变小,则图变成

  Ø -  O  -  O
     /
    ØØ---

现在,比较那些还没有比他们小的两个。 一个选项是上面的最后一个图,可以用剩下的两个比较来解决。 另一种情况是

        ØØ---
       /
  Ø -  O  -  O

在这里,还没有和其他人一起排列的东西,可以通过两次比较来正确放置。

7听起来像它可能是壳sorting以及。

我不认为硬编码的解决scheme应该是复杂的:

  1. 比较(元素)2和3,并根据需要进行交换
  2. 比较3和4,并根据需要进行交换
  3. 比较1和3,如果1less,则比较1和2,否则比较1和4.将1放在正确的插槽中。
  4. 重复步骤3,除了元素3和5。

这将总是使用7个比较。

编辑:

我不认为这会起作用:第4步被打破,可能需要第8次比较。 考虑:

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

步骤4:

  1. 比较3和5 == 4比1 ==元素5less于元素3
  2. 比较2&5 == 3与1 ==元素5less于元素2
  3. ??? 需要比较1和5来知道元素5的放置位置。

铲斗sorting可以如下实现为比较algorithm:

拿一个元素。

将它与所有的桶进行比较。

把它放入相匹配的桶中。 < – 比较需要。

如果未find存储桶,请创build一个新的存储桶。

因此,这是我刚刚描述的dynamic桶sortingalgorithm。

我已经在过去的新闻组上发明/描述了这个。

看看桶sorting。