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(5): Solution based on the O-Sort sorting algorithm | Comment 18 of 20 |
(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

 Search: Search body:
Forums (0)