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(4): Solution based on the OSort sorting algorithm by Erik O.)
That algorithm is quite interesting, as I had never before heard of the Osort. I am wondering what guarantee there is that the array will in fact be in sequence when the sort is finished. I did some experiments, using
length = 10
DIM intArray(length) AS INTEGER
FOR i = 1 TO length
intArray(i) = length  i
NEXT
stp = INT(length / 2  1)
PRINT
WHILE stp > 0
PRINT stp
FOR i = 1 TO length  stp
IF intArray(i) > intArray(i + stp) THEN
SWAP intArray(i), intArray(i + stp)
END IF
NEXT
stp = INT(stp * .86)
WEND
FOR i = 1 TO length
IF intArray(i) < intArray(i  1) THEN COLOR 14: ELSE COLOR 7
PRINT intArray(i);
NEXT
(QuickBasic has a SWAP command that VB lacks, but QB can't use Step as a variable due to its use in the FOR construct.)
With 8 or 9 elements in the array, it doesn't come out sorted:
3
2
1
1 0 2 3 4 5 6 7
3
2
1
2 1 0 3 4 5 6 7 8
(the numbers prior to the display of the array are the step values).
But with larger arrays the numbers always do appear to be sorted correctly. But even that is dependent on the value .86 used to reduce the step each time through. Even changing this to .81 allows some outofsequence numbers to show up. Changing it to even lower values results in even more outofsequence numbers. Is there some theory by which .86 or a certain number thereabouts guarantees correct sorting for array sizes of 10 or more?

Posted by Charlie
on 20040603 13:26:56 