The Naked Scientists

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
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?


 

Offline LeeE

  • Neilep Level Member
  • ******
  • Posts: 3382
    • View Profile
    • Spatial
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
The actual computation time will depend on how smart the compiler is; it may actually produce rather similar code for both the two sources.
 

Offline wolfekeeper

  • Neilep Level Member
  • ******
  • Posts: 1092
  • Thanked: 11 times
    • View Profile
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.
 

Offline LeeE

  • Neilep Level Member
  • ******
  • Posts: 3382
    • View Profile
    • Spatial
Quote
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

  • Guest
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.
 

Offline erickejah

  • Sr. Member
  • ****
  • Posts: 347
  • Parking? I make my own parking spot!!
    • View Profile
You'd need to specify it at a much lower level.

I agree  :)
 

The Naked Scientists Forum


 

SMF 2.0.10 | SMF © 2015, Simple Machines
SMFAds for Free Forums