HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Minimal number of comparisons - sorting $6$ elements

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
sortingnumberelementsminimalcomparisons

Problem

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$.

  1. Merge two subarrays.



Number of comparisons: $3 + 3 - 2 = 4$.

Total number of comparisons: $6 + 4 = 10$.

Solution

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 , $c<d$ and $e<f$ has been asked (3 comparisons) and in case of false proper pair has been swapped:

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.

Context

StackExchange Computer Science Q#47818, answer score: 4

Revisions (0)

No revisions yet.