# The Naked Scientists Forum

### Author Topic: What's the most efficient way to sort a pile by size and colour?  (Read 4795 times)

#### Paul Anderson

• Guest
##### What's the most efficient way to sort a pile by size and colour?
« on: 08/10/2008 10:56:25 »
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

• Neilep Level Member
• Posts: 3382
##### What's the most efficient way to sort a pile by size and colour?
« Reply #1 on: 08/10/2008 18:36:14 »
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

• Guest
##### What's the most efficient way to sort a pile by size and colour?
« Reply #2 on: 09/10/2008 17:53:51 »
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

• Neilep Level Member
• Posts: 1092
• Thanked: 11 times
##### What's the most efficient way to sort a pile by size and colour?
« Reply #3 on: 15/10/2008 05:57:52 »
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:

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

• Neilep Level Member
• Posts: 3382
##### What's the most efficient way to sort a pile by size and colour?
« Reply #4 on: 16/10/2008 01:44:51 »
Quote

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

• Guest
##### What's the most efficient way to sort a pile by size and colour?
« Reply #5 on: 16/10/2008 07:00:21 »
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

• Sr. Member
• Posts: 347
• Parking? I make my own parking spot!!
##### What's the most efficient way to sort a pile by size and colour?
« Reply #6 on: 18/10/2008 17:59:15 »
You'd need to specify it at a much lower level.

I agree

#### The Naked Scientists Forum

##### What's the most efficient way to sort a pile by size and colour?
« Reply #6 on: 18/10/2008 17:59:15 »