This assignment is an activity for groups of three or (if necessary) four. You will be given a balance and eight labeled canisters of different weights. Your goal is to put all the canisters in order from lightest to heaviest, by comparing two at a time in the balance.

Canisters and balance

You will do this twice, each time selecting a different algorithm. You may use one of the algorithms described later in this handout or in the videos, or you may come up with your own technique (as long as you can describe it accurately).

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 (>).

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!)

Illustration of the result of a correct sort

Now that you have completed the sort, place the weights back in the canisters and shuffle the caps so the labels change. Then choose a different technique and sort again.

What to submit

For each sort you do, you should submit all the information in the following template, using the “Write submission” button on Blackboard. One group member may submit on behalf of the entire group, but include everyone’s first and last names.

Group members: Lisa Simpson, Huey Freeman, Meg Griffin

Algorithm name and/or description:
  "Stooge" sort

Comparisons:
  (1) G < C
  (2) D < E
  (3) F < E
  (4) D < F
  (5) ...

Final order:
  A < G < H < B < C < D < F < E

Algorithms

Selection sort

As described in class, or in the Harvard CS50 video: http://www.youtube.com/watch?v=f8hXR_Hvybo. In terms of the balance and canisters, you can work your way through the set, always keeping the lightest canister in the balance. Once you have the lightest canister, you put it first in your sequence and never touch it again. Then you repeat with the remaining ones, always keeping the lightest canister in the balance. It becomes the next in the sequence, and continue until you’re down to the last canister.

Bubble sort

As described in the Computerphile video: http://www.youtube.com/watch?v=kgBjXUE_Nwc. Line up the canisters in a (random) initial sequence. Work through the list, comparing two that are side-by-side. If they were out of order, you swap them when you put them back. After you get to the end of the list, start again at the beginning, and repeat until you make it through the whole way without having to swap.

Merge sort

Also described in the Computerphile video, and in class. Repeatedly split the set in half until you just have a bunch of pairs. Compare those pairs in the balance, and put the lighter one first. Then merge two pairs, comparing the front-most of each repeatedly, to make two sets of four. Finally, merge the two sets of four.

Quick sort

Choose a single canister at random, and leave it in the balance for the first round. This one is called the “pivot.” Compare every other canister to the pivot. If it is lighter than the pivot, place it in a pile on the left. If it is heavier, place it in a pile on the right. Now you know that everything in the left pile comes before the pivot, then the pivot, then everything in the right pile. So choose a new pivot from each pile, and repeat the technique within that pile for the next round.

Bitonic merge sort

Using the diagram on the next page, write your canister identifiers (A–H) in the eight squares across the bottom. Then compare each pair. The lighter canister ID should follow the lighter-shaded arrow up to the next level. The heavier canister should follow the darker-shaded arrow up to the next level. Once all the comparisons at level one are done, start on level two. When you get to the top of the page, the canisters will be sorted.

PDF version

Assignment 4 – sorting