Sorting (ginorst) CPS 004.1, 2 July 2003

Form groups of size two persons. You should start this group activity by introducing yourself. You may also want to choose one person to write down the group's discussion on the provided transparency as you go so that it can be displayed on the classroom's overhead projector.

Specifying an Algorithm

Write an explanation of how to sort a list of words by alphabetical order. Assume that the number of words is not known in advance, but will be between 10 and 600. You are to write an algorithm in English that specifies precisely how to sort the words. This means that you must convey exactly what steps to follow: consider that another group, or the professor/computer, might use your algorithm by following the instructions literally. Thus, saying "put in alphabetical order" is too vague. The end result is a list in alphabetical order, but what procedure should you use to put them in this order? For this exercise, you can assume that your sorting computer knows how to:

determine if one letter is alphabetically before, equal to, or after another
access any single letter in a word according to its place
access any word in a list according to its absolute place (i.e., first, second, tenth, penultimate, last, etc.)
access a word in a list according to its place relative to another (i.e., before, after, next, etc.)
insert a single word any place in a list
determine if there any words in a list
remember a number, letter, word, or list

Keep in mind that your physical space is important. Where do you put things while you are working on other things? For example, think specifically about how you would explain to someone, who can hold only one thing at a time, how to swap two things.

There are many words, so you may want to start by focusing on how to sort a small subset of the words. For example, a one word list is always in sorted order. A two word list is either in sorted order, or the words' order needs to be swapped. Once you understand how the simple cases works, generalize your method to work for any number of words.

Testing your Algorithm

When writing algorithms, it is very easy to make logical errors, i.e., doing a step out of order, doing a step too many times, doing a wrong step, missing a step, or even missing a series of steps to handle a particular case. Thus it is important to test your algorithm on a variety of kinds of lists to have some confidence that it will work for all kinds of lists.

Since it is impractical to test every possible list of words, we choose specific kinds of lists that we think will reveal possible problems. These are called boundary cases because they focus on the edges of our algorithm where we are most likely to make an error. However, instead of building in special steps to handle every one of these cases, you should focus on creating a single, generic procedure that will work for all cases.

To verify that your group's algorithm is correct, test it against these scenarios:

a list of three words in random order
a list of ten word that are already in sorted order
a list of ten words that are in reverse sorted order
a list of twelve words in random order

To test an algorithm using a scenario, you must simulate it as if the sorting computer were following the directions in your algorithm, not another human in your group. In other words, you have to be very careful not to use your common sense to fill in the gaps between the steps. It turns out that a human has to work very hard to be as literal, or dumb, as a computer. This process is called hand-simulation and we will continue to use this technique throughout the semester to verify our programs.

You group should write the results of the test scenarios on a separate sheet of paper. You should also describe any changes to your algorithm that were necessary.

Extra Credit: Adapting your Algorithm

Sorting is one of the most basic algorithms in Computer Science because it is often the difference between a fast program and a slow one. Therefore, it is common that modern sorting algorithms can sort any kind of thing that can be represented with a computer, not just words.

Once your group has created an algorithm, you should adapt it to sort new kinds of things. For example:

a hand of cards
library items by the date they are due back
CDs first by the name of the artist and then year published
25,000 high-school AP exams by student ID number
web pages resulting from a web search based on the number of other web pages that refer to the page

For each of these examples, or change cases, you should consider what changes, if any, are necessary in your sorter and what changes, if any, are necessary in the thing being sorted. One way to characterize these changes is by determining what services, or behavior, your algorithm requires of the things being sorted.

You group should write the results of the change cases on a separate sheet of paper. You should also describe any changes to your algorithm that were necessary.