Math Photo: Sorting Algorithms
One of our end-of-school tasks was breaking down all of our Zometool builds from the past year. When a colleague handed me a bag of several hundred red, blue, and yellow struts, I immediately started to struggle and experiment with the most efficient ways to sort the struts for storage.
Should I take them out of the bag one at a time, placing each in its appropriate pile? Or maybe a handful of ten at a time? Or fifty? Ultimately I settled on dumping them out and sliding them around into color-coordinated piles. I’m not sure of the mathematical justification, but my internal optimizer seemed to think this was the right way to go.
1 Comment
MQ · June 21, 2015 at 7:12 pm
Here’s a good question for students (and teachers): Which of the following two methods is faster? & Why?
(1) Use one hand to move blue struts up while using the other hand to move red struts down.
(2) Use both hands to move all of the blue struts up, and, upon completion, use both hands to move all the red struts down.
(Does one’s answer depend on assumptions about the number of blues and reds? Does knowing the number of each of the three colors indicate that there is a strategy faster than both (1) and (2) above?)