排序与比较的最小数量的数组

本文介绍了排序与比较的最小数量的数组的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我需要一些帮助，我的CS功课。我需要编写排序长度5使用在最坏的情况下7的比较的阵列的排序例程（我已经证明，因为决定树的高度的有7，将需要）。

I need some help with my CS homework. I need to write a sorting routine that sorts an array of length 5 using 7 comparisons in the worst case (I've proven that 7 will be needed, because of the height of the decision tree).

我认为用决策树硬codeD'，但是这意味着该算法非常复杂，是由我的导师暗示，这不是它应该做的方式。

I considered using the decision tree 'hard-coded', but that means the algorithm is really complicated and was hinted by my tutor that's not the way it's supposed to be done.

我检查快速排序，归并排序，堆排序，D-元堆排序，插入排序，选择排序，一律不回答这个要求，这使我相信有需要一种特定的算法长度的数组5。

I've checked quicksort, merge sort, heap sort, d-ary heap sort, insertion sort, selection sort, all do not answer the requirement, which leads me to believe there's a need for a specific algorithm for arrays of length 5.

真的很想得到一些提​​示朝着正确的方向。

Would really like to get some hints towards the right direction.

推荐答案

是的，它是在克努特第3卷第185页（第5.3.1节）。这是第一次在博士论文记录，以便你的教授正在挺难你！有没有真正的简洁大方的方法;你必须跟踪它作为一个部分有序的树。

Yes it is in Knuth vol 3 page 185 (section 5.3.1). This was first documented in a PhD thesis so your Prof is being quite hard on you! There is no really simple elegant method; you have to track it as a partially ordered tree.

这是口齿不清。测试OK（SBCL在Linux上）

Here it is in lisp. Tested OK (SBCL on 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) ))))