Assignment 5 – sorting

due in class on Mon 14 Oct  +40

This assignment is an activity for groups of three or (if necessary) four. We’ll work on it in class on Wed 9 Oct, and then your group must submit one response before the deadline.

Let’s begin by considering all the possibilities that can occur when putting just three canisters in order by weight, from lightest to heaviest. Suppose the canisters are labeled A, B, and C. With three objects, there are 3! (factorial) = 3×2×1 = 6 possible permutations:

1. A < B < C
2. A < C < B
3. B < A < C
4. C < A < B
5. B < C < A
6. C < B < A

So we can think of the role of a sorting algorithm as determining which of the possible permutations is the correct one.

Suppose we begin by placing A and B on the scales, as illustrated by the root node “A,B” in the tree below. There are two possibilities, shown as arrows from the root node: either A is lighter than B, or B is lighter than A. (Throughout this exercise, we’ll assume that no two canisters are exactly equal in weight.)

After each branch, we must determine whether to do another comparison (as in the oval “B,C”) or whether the correct order is now known (as in the rectangle “A < B < C”).

Question 1: Complete the tree above, showing what additional comparisons need to be made, and what ordering you can conclude at each leaf. Your tree must show all six possible permutations. Continue to use ovals for comparisons, rectangles for results, and label the arrows with comparisons like “C < A”.

Question 2: In the remainder of this exercise, you’ll put 8 canisters in order by weight. How many possible permutations are there?

Now let’s move on to the main event. Your goal is to put all the canisters in order from lightest to heaviest, by comparing two at a time in the balance. As you work, you should:

• Neatly write down the result of each comparison, numbered in the order you do them. Always write the label of the lighter canister on the left, as in “(1) H < C” or “(2) D < A” – do not use greater-than (>).

• Think carefully about the strategy you are using, because afterwards you will write it down in such a way that it could be repeated by other humans. Try not to change strategies in the middle.

• Do not estimate which canister is lighter just by picking them up – that counts as a comparison and would also have to be written down! So always use the balance.

Once you have committed to an ordering, write that down as well: all eight letters from lightest to heaviest. Then you can verify your work by carefully opening the canisters and counting the weights inside, as illustrated. (Do not lose any of the pieces!)

Now that you have completed the sort, place the weights back in the canisters and shuffle the caps so the labels change. Talk about your technique, and write it down carefully. Then try to come up with a different technique and sort again.

You can use the extra sheets to record your results.

PDF version