All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Yet one more coin sorting problem (Posted on 2004-05-31)
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?

 See The Solution Submitted by Federico Kereki Rating: 4.0000 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 re(6): Solution based on the O-Sort sorting algorithm | Comment 19 of 20 |
(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

 Search: Search body:
Forums (0)