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

Home > Logic > Weights and Scales
Yet one more coin sorting problem (Posted on 2004-05-31) Difficulty: 3 of 5
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.)
Question 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information