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.