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