sort 4 elements with 3 comparisons (not a homework question)

2b97deded6213469bcd87b65cce5d014
0
Mihail121 102 Jan 17, 2009 at 15:55

Now I’ve had a friend over telling me one could sort 4 elements (balls for ex.) using 3 measurments with a standard scale. I tried and tried and TRIED but I just can’t do it. Does anyone have an idea how would it be possible?

2 Replies

Please log in or register to post a reply.

B91eae75cd6245bd8074bd0c3f1cc495
0
Nils_Pipenbrinck 101 Jan 17, 2009 at 18:43

It’s not possible. The minimum number of compare and swap-operations you need is five (assuming the data is not already partly sorted).

3c5be51fdeec526e1f232d6b68cc0954
0
Sol_HSA 119 Jan 17, 2009 at 20:46

Depends on how you define measurements. spaghetti sort could definitely do it.. =)