CSC152 2006S, Class 46: Sorting
Admin:
* Homework 16: Approximate String Matching.
* We'll try the mini-Titular Head again tomorrow.
* Advance notice: Exam 3 distributed Friday.
* Taking more CS?
* Natural fall course: CSC223 (Software Design) (Staff)
* Alternate fall course: CSC205 (Computational Linguistics) (Stone)
Overview:
* The Problem of Sorting.
* Carefully Specifying Sorting Methods.
* Testing Sorting Methods.
What does it mean to sort?
* Given a collection, put the elements in a particular order
* What do we mean by a collection?
* Array
* Vector
* Sequenced Lists
* What do we mean by "in order"?
* "According to a comparator"
* c.compare(a[i],a[i+1]) <= 0 for all reasonable i
* c.compare(v.get(i),v.get(i+1)) <= 0 for all reasonable i
* c.compare(l.get(pos),l.get(l.successor(pos))) <= 0
* Using the "internal comparator" of Comparables
* a[i].compareTo(a[i+1]) <= 0 for all reasonable i
* We should be able to predict the order in which the elements appear
* Questions when designing a sorting algorithm:
* What are we sorting? For this class: Vectors
* How do we compare? For this class: Using a Comparator
* In-place (mutate)? New vector (maybe some in-place examples, too)
* Stable? If A precedes B before the sort, and A = B, where does A appear after the sort? Not required, but analyzed.
* Example: Sort by date, then sort by name. Within each name, a stable sort keeps them sorted by date.
public interface Sorter
/**
* Sort a vector in increasing order.
*
* @param vec
* The vector to be sorted.
* @param c
* The comparator that determines the order.
* @return sorted
* The sorted version of vec.
* @pre
* The vector is non-empty. (vec.length() > 0)
* The comparator should be applicable to any two elements in vec.
* (c.compare(vec.get(i),vec.get(j)) does not throw an
* exception for any valid i and j).
* The comparator is transitive and reflexive and all that stuff.
* @post
* sorted is sorted.
* c.compare(vec.get(i),vec.get(i+1)) <= 0 for any reasonable i
* (0 <= i < vec.length()-1)
* sorted is a permutation of vec.
*/
public Vector sort(Vector vec, Comparator c);
}
Black-box testing: What tests do you want to run?
* Give it one vector and see if it sorts correctly.
* Use human brain.
* Automate testing:
* Is it sorted?
public boolean sorted(Vector vec, Comparator c)
{
for (int i = 0 ; i < vec.length()-1; i++) {
if (c.compare(vec.get(i),vec.get(i+1)) > 0) {
return false;
}
} // for
return true;
}
* Is it a permutation?
Put each element in a dictionary (one for original list, one for sorted list) with a counter , ...
* Start with a sorted vector.
* Make a copy and permute the copy
* Ask to sort the permuted copy
* Give it a presorted vector and see if it comes out unchanged.
* Try a variety of lengths
* Try with and without duplicates
* How would you permute the copy of the already-sorted vector?
* Repeatedly
* Use a random number generator
* Use that rng to pick positions
* Swap the values at that positions