CSC152 2005F, Class 51: An Introduction to Sorting Admin: * Textbook or Java reference next semester? * Questions on the exam? * Changes to schedule Overview: * The problem of sorting * Variations * Careful specs * Testing Books * How do I search the eboards? * cd /home/rebelsky/Web/Courses/CSC152/2005F/EBoards * grep string *.txt * Need more examples! (A textbook would help, or would pointers to sites.) * Recommend, don't require Getting the depth of a tree static int depth(TreeNode tn) { if (tn == null) return 0; else { int leftdepth = depth(tn.left); int rightdepth = depth(tn.right); if (leftdepth > rightdepth) { return 1 + leftdepth; } else { return 1 + rightdepth; } } } What's the "or" command? if ((foo) || (bar)) On to Sorting * Problem: Given some form of collection, put the values in order (typically from smallest to largest) * Design issue: Collection might be array, vector, list, ... * Sorting routines for vectors and arrays look similar * Sorting routines for lists are different than those for the other two * Design issue: Effect on original array/vector/list? (define foo (list .....)) (sort foo) (display foo) ; What do you expect to see? ; A sorted version of the original list (sort!) ; The original list - sort *returns* a sorted version (sort) * Sorting that mutates is "in-place" * Good in-place routines use only a little extra memory (not just "sort out of place and copy back") * Sorting that does not mutate is "not in-place" ("out of place") * Design issue: Comparison? "By what do I sort?" * "By the natural order" * Using a comparator * Is the comparator a parameter to the sort method or a field of the class? Our focus: Sort Vectors in-place using comparator specified as parameter public interface Sorter { /** * Sort vec using order to compare elements. * * @pre * order must be applicable to any two elements * in vec. * @post * Elements are in order, according to order. * That is, for all reasonable i * order.compare(vec.get(i),vec.get(i+1)) <= 0 * @post * All the elements in the original vector need * to be in the result. No elements are added * or removed. * A mathematician would say "the result is a * permutation of the original" * @post * @post */ void sort(Vector vec, Comparator order) } Black-box testing: I hand you a .class that implements this method. You do not have access to the source code (or I write code so impenatrable that you can't understand it). How can you be confident that it works? * Try a variety of calls * Different types (strings, integers, students) * Different comparators (string-size, string-alphabetic, student-grade, student-height) * Variety of values (e.g., positive and negative integers; men and women; lowercase and mixed-case strings) * Different sizes * DON'T RELY ON YOUR EYES ... LET THE COMPUTER DO THE COMPARISON! * After each call, test both postconditions. * Make sure it's ordered. (See exam 2 for sample code.) * Make sure it's a permutation. (Ask Cole.) * Trick: Start with a sorted vector. Clone (copy) it. Randomize the clone and sort it. Compare to the original.