You have five coins, apparently alike, but actually of different weights. You also have a two arm scale.

Can you manage to sort the coins in ascending order, using the scale only seven times?

Bonus question: can it be done in fewer weighings?

(In reply to re(5): Solution based on the O-Sort sorting algorithm by Charlie)

The magic number .86 comes from trial and error while I was developing the sorting algorithm.  Using an array of 10,000, I discovered that .85 doesn't assure a complete sort, but .86 worked every time for the 100+ times I ran it.  That's still no guarantee, but I'd say that's pretty good odds.

I suspect that it may be more consistant to replace that initial step=int(length/2-1) with step=.86*len(array)

I made a modification to this version of the O-Sort to use a floating point variable for the step size decrment and was able to get consistent results using .78 as the decrement multiplier.

To see more on what I did check out:  http://www.geocities.com/oosterwal/computer\sortroutines.html

I hope it's ok to stick links like that in here...

My basic theory behind the algorithm is that by using a large step size at the beginning, you are able to swap small numbers from the upper end of the array to the bottom quickly and large numebrs from the lower end of the array to the top quickly.

I hate to admit it, but my first version, which decremented step by only 1 during each loop, had a performance that was even worse than a Bubble sort.

Posted by Erik on 2004-06-03 17:44:31