Outline 30: An Introduction to Sorting

Held: Monday, 28 October 2013

Summary

We consider the well-known problem of sorting.

Related Pages

Overview

Administrivia

I will return exam 1 at the end of class. (Stop me when there are ten minutes to go.) You may submit a makeup by Thursday night.
I returned HW 6. I still plan to grade HW 5. I will not grade HW 2-4, but will give you all checks. (Sorry, it doesn't seem worth grading at this point.)
Today we will continue the approach of "think for a few minutes, share with the class, repeat".
Upcoming extra credit opportunities:
- Learning from Alumni, Thursday: Jordan Shkolnick '11 (Microsoft)
- CS Extras, Thursday: ???
- CS Table, Friday:

The problem of sorting

Goal: Given a collection of values, put them in order.
How do you decide what order?
- Sometimes we use the natural ordering.
- Sometimes we use a comparator.

We'll build a sorter interface.
- Will the individual objects ever need more than one copy? Probably not. We'll see how to handle that issue later.
The basic method: Sort an array of T's using an appropriate comparator.
I'll ask you to fill in the blanks (preconditions, postconditions, etc.)

How do we test a sorter?
Three basic approaches:
- Systematically generate a lot of samples and see that it works on all of them
- Randomly generate a lot of samples and see that it works on all of them
- Perhaps do a few special cases
How do we know that a sort method has succeeded?
- The result is in order
- The result is a permutation of the original array
We can check these by writing inOrder and isPermutation predicates, but those are a pain.
A better strategy:
- Start with a sorted array.
- Make a copy.
- Permute the copy.
- Sort the permuted copy.
- Compare to the original array.
For the random samples approach, we just need a "randomly permute" method.
For the systematic approach, we might want to make all permutations. But how?