Lesson 8: Sorting
This lesson adapted from Computer Science Unplugged (c) 1998, by Bell, Witten, and Fellows. See http://unplugged.canterbury.ac.nz/ for copyright restrictions.

Motivation:

Data is most easily searched if it is first placed in some order, for example alphabetical, numerical, or chronological. Computer scientists study the process of putting the data in order. In this lesson we examine several sorting (or ordering) techniques, and discover that a clever technique works much more quickly than a simple intuitive one.

Materials:

  1. Sets of eight or so film canisters with increasing numbers of pennies inside, labeled with symbols or letters which do not reveal the number of coins within -- one set for each small group of students.
  2. Balance scale for each small group of students.

Lesson Plan:

  1. Explain that the way computer scientists generally refer to sorting is different than the way you think of sorting when you do your laundry. For computer scientists, sorting means putting things in order, rather than just separating things by category.
  2. See if students can think of places where sorting is important (telephone book, dictionary, book index, library, addresses, are just a few examples). Ask them to imagine how hard it would be to find a friend's name in the phone book if the names weren't sorted! (If you did the lesson on searching, you will already have discussed this.)
  3. Continue with Activity 7: Lightest and Heaviest from Computer Science Unplugged.

Conclusion:

The relative efficiency of each sorting method becomes more obvious when a larger number of items are being sorted. For example, if we were sorting 50 cards, selection sort would require 1225 comparisons, whereas quicksort would require about 271 on average!! (You may need to note the fact that these comparisons largely determine the length of time it takes to do the sorting)

Evaluation:

There are two terrific opportunities to assess the students' understanding in this lesson. The first is to have the class analyze the number of comparisons required to sort the canisters. What was the average number of comparisons for the whole class? Break down the data by algorithm type and check to see if one algorithm is on average faster than the others. The students may come up with their own questions to answer using the data.

Second, the written descriptions of the sorting strategies should be read using a holistic scoring method. For example, papers may first be sorted into stacks that might be labeled "missed the point", "acceptable", and "has some special quality". Those stacks can then be divided again into two levels each. This method encourages examination of students' thinking rather than small bits of knowledge, and it minimizes the need for structuring questions to elicit predetermined answers.

Extensions:

Slightly more advanced students can calculate the exact number of comparisons used by selection sort when sorting n items. The first pass requires n-1 comparisons, the second n-2, etc. Summing these values gives n(n-1)/2 total comparisons, which is proportional to n2. The best sorting algorithms take time proportional to only n log2 n to sort n items, which is a considerable improvement. Have the students graph the two functions n2 and n log2 n, or just compute the difference in values for large numbers n (e.g., n = 100 or 1000 or 1,000,000).

There are a number of other sorting techniques to compare. As a research project, students could find other techniques in the literature and demonstrate them to the rest of the class. Some other common sorting algorithms are bubble sort,merge sort, shell sort, radix sort, bucket sort, heap sort.

For any of these sorting methods, or the ones discussed above, it is both fun and helpful to have the students sort themselves using the method. This can be done by height, birthday, alphabetically by name, or with cards held by the students showing some assigned value. (Presenting an opportunity to practice any valuation skill you have in mind - e.g., sort a collection of mixed fractions and decimal numbers.)

Related Links:

  • Sorting Algorithms -- a very nice collection of java applets that visually demonstrate a large number of different sorting algorithms.

Standards:

  • NCTM K-4:  1, 2, 3, 4, 5, 10, 11, 13.
  • NCTM 5-8:  1, 2, 3, 4, 7, 8, 10, 13.
  • NCTM 9-12:  1, 2, 3, 4, 10, 12.

Skills:

  • Problem solving / reasoning / communication / connections
  • Strategy development
  • Measurement - use of balance scales
  • Classification by "greater than" and "less than"
  • Record keeping
This lesson adapted from Computer Science Unplugged (c) 1998, by Bell, Witten, and Fellows. See http://unplugged.canterbury.ac.nz/ for copyright restrictions.