[Paul Anderson]

Paul Anderson  asked the Naked Scientists:

Hi Chris and team,
 
If you have a mixed pile of big and small, white and black buttons, and you are writing a computer program to sort them, I am of the opinion that you either sort by colour first and then sort by size, or vice versa? Is there a faster way which involves less computation?
 
Is it large?
If Y put in bag L otherwise put in bag S
 
And then sorting bag L
Is it white?
If Y put in bag LW otherwise put in bag LB
 
Then sorting bag S
Is it white?
If Y put in bag SW otherwise put in bag SB
 
If you were to say:
Is it black and large?
If Y put in bag LB

This now leaves you with B&S, W&S, W&L, so you still have to sort for 3 other possibilities, so you haven't achieved any economy by tackling it that way.
 
Maybe this doesn't really fit in with the Naked Scientist programme, but it's an idle thing I have considered in the past.
 
Regards
 
Paul
NZ

What do you think?

[LeeE]

Where you know that you will only ever get large or small, black or white you could use:

IF large then {
  IF black then {
    put in large black bag;
  } ELSE {
    put in large white bag;
  }
} ELSE {
  IF black {
    put in small black bag;
  } ELSE {
    put in small white bag;
  }
}

If there's a chance of other colours or sizes of buttons you'd probably be better off doing something like:

CASE (large AND black) { put in large black bag }
CASE (large AND white) { put in large white bag }
CASE (small AND black) { put in small black bag }
CASE (small AND white) { put in small white bag }
CASE () {put in others bag}

[lyner]

The actual computation time will depend on how smart the compiler is; it may actually produce rather similar code for both the two sources.

[wolfekeeper]

The quickest way to do this kind of thing in general that I'm aware of is to use an index sort.

In other words, you convert the size into 0 or 1 (where 0 is small, 1 is big) and the colour into 0 or 1 as well.

you then just add the sock into an array something like:

sock[size][colour].add(sock)

As others have noted it may not be quicker, it will depend on the compiler and stuff. It probably would be quicker if there were more types of socks though than just 4.

[LeeE]

sock[size][colour].add(sock)

Umm... where did the socks come from?  They should have been rejected by data validation, as we're dealing with buttons.

But here you're just using a sock class that you assume has add, and presumably sort, methods without showing the corresponding algorithms for the methods.  This answer is like saying the best way to sort the buttons (or socks) is to use the sort method.

[lyner]

those are essentially high level language instructions. Quick ways to tell the machine what you want done. I Assumed we were looking for a routine which was optimal for the particular operation. You'd need to specify it at a much lower level.

[erickejah]

You'd need to specify it at a much lower level.

I agree  []