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 O-Sort sorting algorithm by Erik O.)

That algorithm is quite interesting, as I had never before heard of the O-sort.  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 out-of-sequence numbers to show up. Changing it to even lower values results in even more out-of-sequence 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 2004-06-03 13:26:56