-3
$\begingroup$

enter image description here

What is the average number of comparisons performed when sorting 3 items?

The question is based on the above picture.

$\endgroup$
1
  • $\begingroup$ The answer is fairly obvious from the comparison tree. What are you missing ? $\endgroup$
    – user16034
    Jul 4, 2022 at 8:22

3 Answers 3

1
$\begingroup$

There are six possible orderings of three numbers. You can distinguish between six states with two 2-bit codes and four 3-bit codes; that is the lower bound if all orderings are equally likely. Average number of bits = 2 2/3rds.

Since you can’t have arbitrary tests but only comparisons between two items, you won’t be able to achieve the lower bound for larger numbers of items.

$\endgroup$
1
$\begingroup$

You haven't defined what you mean by average, so let me assume that the average is taken over all permutations of some fixed array consisting of three distinct numbers (the exact numbers don't matter, since the result will be the same).

Denote the number of comparisons performed on an array $A$ by $C(A)$. Then the average number of comparisons is $$ \frac{C(1,2,3) + C(1,3,2) + C(2,1,3) + C(2,3,1) + C(3,1,2) + C(3,2,1)}{6}. $$

$\endgroup$
1
$\begingroup$

$$\frac{2\cdot 2+4\cdot 3}6.$$

$\endgroup$

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.