我的 CS 作业需要一些帮助.我需要编写一个排序例程,在最坏的情况下使用 7 次比较对长度为 5 的数组进行排序(我已经证明需要 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).
我考虑过使用硬编码"决策树,但这意味着算法真的很复杂,而且我的导师暗示这不是应该的方式.
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-ary 堆排序、插入排序、选择排序,都没有满足要求,这让我相信需要一个特定的算法来处理长度的数组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.
推荐答案是的,它在 Knuth vol 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.
这里是 lisp.测试正常(Linux 上的 SBCL)
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) ))))更多推荐
以最少的比较次数对数组进行排序
发布评论