Menu
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.
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.
673
Merge-insertion sort is the sorting algorithm with the minimum possible comparisons for n items whenever n ≤ 15 or 20 ≤ n ≤ 22, and it has the fewest comparisons known for n ≤ 46. Glenn K.
(4 factorial) If you do only 4 comparisons, then you can get only 4 bits of information, which is enough to distinguish between 16 different cases, which isn't enough to cover all the possible output cases. Therefore, 5 comparisons is the optimal worst case.
The graph will now contain many non-intersecting cycles. Now a cycle with 2 nodes will only require 1 swap to reach the correct ordering, similarly, a cycle with 3 nodes will only require 2 swaps to do so. Hence, ans = Σi=1k(cycle_size – 1)
That will always use 7 comparisons.
Donald Knuth's The Art of Computer Programming, volume 3 has a section on exactly this topic. I don't have the books here with me, but I'm pretty sure Knuth presents the algorithm for 5 elements. As you suspect, there isn't a general algorithm that gives the minimal number of comparisons for many sizes, but there are a number of common tricks that are used in such algorithms.
From vague recollections, I reconstructed the algorithm for 5 elements, and it can be done in 7 comparisons. First, take two separate pairs, compare inside those, and compare the smaller ones of each pair. Then, compare the remaining one against the larger of these. This now splits into two cases according to whether the remaining element was smaller or larger, but in all cases it's possible to finish in the three comparisons still available.
I recommend drawing pictures to help you. Knuth's pictures are something like this:
o---o / o---o
which shows the results after the first three comparisons (and from what I recall, this kind of a picture appears in many minimal-comparison sorts). A line connects two elements whose order we know. Having such pictures helps you in determining which elements to compare against, as you want to make a comparison that gives you the maximal amount of information.
Addendum: Since there is an accepted answer with actual code, I guess there's no harm in finishing up these diagrams, and they might be a useful addition to the answer. So, start with the above one, and compare the missing element against the one on the top left. If it is larger, this will lead to
/--o o / \--o o \--o
Now, compare the two large elements at the top right and we end up with
o---o---o / o---o
Now, by comparing the bottom right element first against the middle one on top and then against whichever side it belongs on, we place it correctly using the remaining two comparisons.
If the initial comparison resulted in the remaining element being smaller, the diagram becomes
o---o---o / o---o
Now, compare the two that have yet nothing smaller than them. One option is the last diagram above, which is solvable with the remaining two comparisons. The other case is
o---o / o---o---o
And here again, the one that is not yet in sequence with the others can be placed correctly with two comparisons.
145
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.
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) )))) If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
