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