Handout 10B

The purpose of this exercise is to study the bubble sort algorithm and introduce the notion of efficiency of an algorithm.

Choose a number and write it down on a piece of paper. Don't let your neighbor know what number you chose, but write your number large enough that your classmates could see it from across the room if you let them.

Once everyone in the class has chosen a number, pick up your number and stand in a line with the rest of the class. The object of this exercise is to apply the bubble sort algorithm to sort the numbers held by the students.

Decide which end of the line should have the largest numbers and which should have the smallest numbers.

Sort yourselves following these rules:

  1. You can only compare your number with the numbers of the people next to you in line.
  2. The only move you can make is to change places with a person next to you in line.
  3. You can't compare numbers with a person or trade places with them while they're moving or comparing numbers with someone else.
When the list is sorted, the student at the "low" end of the line should call out their number, then the next, then the next, up to the high end of the line. If the line is sorted correctly you may choose new numbers and sort again. If not, try again to sort the line while following the rules above.

Assuming that it takes a fixed amount of time to compare two numbers and to trade places, what things could you do to speed up the sorting process while still following the rules? What if you were allowed to break the rules?

It was probably pretty easy for you to to sort the line of students. You might have used a simple algorithm like:
  1. Compare your number to the person to the left of you.
  2. If your number is lower than theirs, trade places.
You probably even found an algorithm that gets around rule 3 better than this one does. Your algorithm was probably pretty efficient, because you could have several pairs of people comparing their numbers at the same time. In computer terms this would be called "parallel processing"; most computers are not designed to run algorithms that require parallel processing.

There is a much less efficient algorithm that follows the rules above that can be programmed in LOGO. This is the bubble sort algorithm. A pseudocode description of the bubble sort is given below, and you can also study the bubble sort animation at http://max.cs.kzoo.edu/~abrady/java/sorting/.

  1. Use some index, say I to keep track of where in the list you are.
  2. Start with I pointing to the last number in the list.
  3. If the I-1st number is bigger than the Ith number, swap the I-1st and Ith numbers in the list.
  4. Change I to point to the I-1st number in the list.
  5. Repeat from step 3.
Draw a flow chart describing the bubble sort. Write a LOGO program that uses the bubble sort to sort a list of numbers.

Mtht420