if you can sort 5 numbers in 7 comparisons, how to sort 6 numbers in 10 comparisons?

There is another question on sorting 5 numbers in 7 co开发者_StackOverflow中文版mparisons:

Sorting an array with minimal number of comparisons

My question is about sorting 6 numbers in 10 comparisons.

You can do it in 12 trivially:

• Sort the first 5 numbers with 7 comparions
• Compare the final number with each of the first 5, to determine its position

You could do it in better than that using a binary search, of course... compare the final number with the middle of the 5, then with the first two or last two depending on the result of that comparison. This should end up with 10 comparisons at most.

The fastest way to do it (with the least possible average number of comparisons equal to the theoretical value) is:

c1 -→ o  | 3/10 comparisons
c2 -→ o
o -→ o

Then after comparison of two bigger numbers (c1 and c2) we have

o -→ c1

o -→ o -→ c2 | 4/10 comparisons
 ↘
   ↘o

Then we compare "c1" to "c2" and get two possible variants (first if c1 > c2, otherwise second one)

A)Worse(26/45 of all cases)  B)Better(19/45)   | 5/10 comparisons

o -→ c1 -↘                             b-↘
           ↘                               ↘
  o -→ c2 -→ o                o -→ c1-→ c2-→ c3
   ↘                           ↘  
     ↘o                          ↘a

A) In the first case our next step will be comparison of "c1" to "c2" after what we can get A1) if c1>c2 otherwise A2)

A1)                       A2)                 | 6/10
       o↘                 c1-→ c2 -→ o -→ o
          ↘                        ↗
 o -→ c1-→ c2 -→ c3              a -→ b
  ↘
    ↘a

A1) We sort "a" in sequence {c1;c2;c3} starting with comparison to c2, then we get

A1.1)                     A1.2)               | 8/10
       a↘                            a↘
          ↘                             ↘
 c1-→ c2-→ o -→ o -→ o     c1-→ c2-→ c3-→ o -→ o 

A1)Then we have only to sort "a" in sequence {c1;c2} or {c1;c2;c3} starting in both(!) A1.1 and A1.2 cases with comparison to "c2" in 1-2 (A1) or 2 (A2) comparisons.

A2) We sort "a" in {c1;c2} always starting with comparison to c1, then we sort "b" in a sequence of elements which are smaller then "a" starting with comparing to any element(if there are 2) , 2nd (if there are 3), any of 2nd or 3rd(if there 4 elements in that sequence)

B) The same way as above we sort "a" in a sequence {c1;c2;c3} starting with comparison to c2, after that we sort "b" in a sequence of elements smaller than c3 starting with comparison to c2(if there are 3 elements) or to c2 or c3 (if there are 4). This will take 3-4 comparisons. You can also do vice versa starting with "b", the result won't change.

In total, this algorithm sorts 6 numbers in 9 comparisons in 19/45 cases and in 10 comparisons in 26/45 cases.

Minute of theory

6!=720, 2^9=512, that means after 9 comparisons we can have 512 different results, so for 304 (304 is 512 - 2*(720-512)) of them we can say "that's all, we definitely know the order", but for the 208 rest we need one more comparison to distinct them from 208 another disposals with the same comparison results. 304/720 = 19/45; 208*2 / 720 = 26/45 ~ 0.578 So the best possible algorithm will have 9.578 comparisons on average. There is another option: sort 5 in 7 comparisons and sort 6th element in 3 comparisons afterwards, but since "5 in 7" best algorithm is sorting in 6 comparisons in 1/15 of cases, "6 in 10" algorithm will sort in 8 comparison in 1/45 cases (9 comparisons in 16/45 cases, 10 comparisons in 28/45 cases) leading to 9.6 comparisons on average.

I believe you can do better than 13, just on the principle of O(n log n) growth.

The basic approach is that you design a decision tree that determines which permutation you're dealing with, but not sensitive to actual values. But assuming that an exhaustive search of possible decision trees is needed to find an optimal one, you need to be aware that as the number of items increases, the number of decision trees to consider increases very quickly. At a guess exponentially, though I haven't checked that guess - it may even be worse than that.

You may be able to do better than 13 by just hard-coding the tests that a common sort algorithm - but not an O(n^2) algorithm such as bubble-sort or even (I suspect) quicksort.

Basically, I think the idea is more trouble than its worth. Five is probably the practical limit for a hard-coded optimal sort. Anything larger - just use a standard sort algorithm. Though I'll bet someone will answer with an implementation anyway.