Hi, this is not a homework assignment... my school prof just wanted us to solve the problem so we can discuss it in class as a group. English is my second language and this question is quite tough for me... It would be great if you can help. Thank you~

first) Tommy is a 7 year old boy. In his room is a shelf with 10 boxes of toys. His mother made him organized his toys and she helped him placed a piece of masking tape on the bottom of each of the 10 boxes specifying what is in them (e.g. balls, action figures, games, etc.). One day his mother decided to clean Tommy's room. Now she wants to sort the boxes according to what is in them, from left to right so that the leftmost box is the one whole name specifying what is in it comes first alphabetically. Assume that the mother can pick up only 1 box in each hand at a time and that the box must either be in the mother's hand or on the shelf (that is, she cannot put them down anywhere else). Note that the mother may pick one box up in her hand and slide another box along the shelf with her free hand. Explain in plain English (i.e. give an algorithm) how the mother can sort the boxes properly.

second )Assume now there are exactly two shelfs and that the mother can make use of the second shelf to place the boxes on. Can you describe a better way of sorting the boxes ? Perhaps there is a quicker way or a way that involves the use of only one hand.

Thanks for your help!

06-05-2006, 07:57 AM

nspils

You are being asked to discuss two different sort algorithms. The first allows you to compare the box of interest with only the next box and, if it is "larger" than the next box, to slide the next box forward in line and put the box of interest into the space vacated by the next box. The largest in the group will bubble its way up the line to the end. Then you return to the current first box in the line and do your comparisons again up the line until the second largest is at the second from the end position. An so on.

With the second sort, you get to take the items one at a time and insert them into alphabetical order in the second line.