5
$\begingroup$

I've been thinking about sorting $6$ elements with the minimal possible number of comparisons. I can do it in $10$ comparisons but I've no idea if this is optimal. Or is there a better algorithm ?

Algorithm
1. Sort $a_1, a_2, a_3$ and $a_4, a_5, a_6$.
Number of comparisons: $3+3=6$.
2. Merge two subarrays.
Number of comparisons: $3 + 3 - 2 = 4$.
Total number of comparisons: $6 + 4 = 10$.

$\endgroup$
5
  • 1
    $\begingroup$ Closely related question. In my answer there, I give a reference to the relevant section in TAoCP. What research have you done? $\endgroup$
    – Raphael
    Oct 3, 2015 at 10:48
  • $\begingroup$ How does step 2 take only 4 comparisons? ​ ​ $\endgroup$
    – user12859
    Oct 3, 2015 at 12:04
  • $\begingroup$ You are right, I am wrong.... How to fix it ? $\endgroup$
    – user40545
    Oct 3, 2015 at 22:31
  • $\begingroup$ See, for example, Daniel Fischer's answer in Exactly how many comparisons does merge sort make?. $\endgroup$
    – greybeard
    Oct 4, 2015 at 7:01
  • $\begingroup$ Ok, I know that I was wrong. I think about fixing my algorithm. $\endgroup$
    – user40545
    Oct 4, 2015 at 8:24

2 Answers 2

0
$\begingroup$

According to A036604, 10 comparisons are indeed optimal. The link probably contains a citation to a paper proving this.

$\endgroup$
4
  • $\begingroup$ @user40545 I don't know, but I believe you can verify that yourself. $\endgroup$ Oct 3, 2015 at 8:21
  • $\begingroup$ Ok, hovewer it is sufficient to analyze decison tree to prove optimality ? ($log(6!)\ge 10$) $\endgroup$
    – user40545
    Oct 3, 2015 at 8:22
  • 1
    $\begingroup$ @user40545 You can do this calculation and see for yourself. Try to be more independent. $\endgroup$ Oct 3, 2015 at 8:24
  • $\begingroup$ I thnik you are right, I am too dependent. $\endgroup$
    – user40545
    Oct 3, 2015 at 8:30
4
$\begingroup$

TL-DR; $10$

Yes, you need to have possibility to ask up to $10$ questions to (comparison) sort an array of $6$ elements.

However, it is possible to create an optimal algorithm that will require no more than 10 questions in worst case, but in average only $9.57777$ questions (in $416$ cases $10$ comparisons, in $304$ cases only $9$).

Here is a decision tree for sorting 6 element arrays [a,b,c,d,e,f]. To make it more compressed. I assumed that already $a<b$ , $c<d$ and $e<f$ has been asked (3 comparisons) and in case of false proper pair has been swapped: Compressed DT for sorting 6 elements As you can see, in addition to these 3 comparisons, we need up to 7 more, but often only 6 that gives us the $9.57777$ in average.

$\endgroup$
3
  • 1
    $\begingroup$ Can you perhaps describe how that algorithm works? It would be great to see some elaboration/justification on the number you are listing. $\endgroup$
    – D.W.
    May 3, 2023 at 20:34
  • $\begingroup$ @D.W. it is based on my own research. Not yet published, but you can ping me on priv: [email protected] for more details. $\endgroup$ May 5, 2023 at 17:54
  • $\begingroup$ @D.W. I've added example decision tree for you. Cheers! $\endgroup$ May 5, 2023 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.