CSC152 2005S, Class 49: Sorting

Admin:
* Feel better Cassie!
* Math/CS picnic

Overview:
* Basics of the problem
  * What it means to sort
  * Variants
* Specify!
  * Formally
  * Write Java
* Begin to design algorithms

Algorithm: Instructions for completing a task
Sorting: Given a collection of objects, put them "in order" (typically from smallest to largest) s.t.
  object 0 <= object 1 <= object 2 <= .... <= object n
Also: Do it quickly!

Many design questions:
* What is the "collection"?
  * Array
  * Vector
  * List
  * ...
* What happens to the original data?
  * "In place" sorting: We rearrange the original collection
  * "Out of place" sorting: We build a new, sorted collection and DO NOT AFFECT THE ORIGINAL
* Does the original arrangement affect the results?
  * Suppose a appears before b in the unsorted collection AND a "equals" b, what is the relationship of a and b in the sorted collection?
    * Stable sort: a remains before b (Stable sort preserves order, where possible)
    * Unstable sort: Who knows?
  * Why would anyone care that a sort was "stable", given that it's doing a lot of rearrangement?
    * Example: We might have the original collection in "insertion order" and want to maintain that wherever possible.  (A priority queue with queue-like behavior.)
    * Lets us combine sorts : 
      * For a group of people sorted by "first name, but if two peoploe have the same first name, order them by last name", we can "sort by last name" then "sort by first name"

Our goal in this class: Normally in-place, sometimes out-of-place, normally ask about stability afterwards.

/Formalizing the Notion of Sorting/

Procedure: 
  outOfPlaceArraySort
Parameters:
  a, an array with values a_0 ... a_(n-1)
  c, The thing we're sorting by (Comparator)
Purpose:
  Arrange a into incrasing order by c.
Produces:
  s, a sorted array
Preconditions:
  c must be applicable to the values in a 
    In Java, c.compare(a[i],a[j]) must work for all i and j
    0 <= i,j < a.length
  // c must be transitive, reflexive, and symmetrical, but that's part of the definition of comparators
  a must be nonempty
Postconditions:
  a has not changed
  s is sorted in increasing order
    c.compare(a[i],a[i+1]) <= 0 for i, 0 <= i < s.length-1
  s is a permutation of a

// Sam's hack solutions given the initial specification:
  return "a new empty array"  O(1)
  return "a new array of the same size as a that contains lots of copies of a[0]" O(n)

* Detour: transitivity
  suppose x < y and y < z, what does that tell us about the relationshyip of x and z?
  * If < is transitive, x < z
  * If < is not transitive, anything goes
* Detour: reflexivity:
  x < y impliies y > x
* Detour: Whatever term rolf used
  x = x

Time for Java
public interface OutOfPlaceArraySorter
{
  public Object[] sort(Object[] a, Comparator c);
}

public interface InPlaceArraySorter
{
  public void sort(Object[] a, Comparator c);
}

public interface OutOfPlaceVectorSorter<T>
{
  public Vector<T> sort(Vector<T> a, Comparator<T> c);
}

public interface InPlaceVectorSorter<T>
{
  public void sort(Vector<T> a, Comparator<T> c);
}

The latter form gives us one of the preconditions "for free"
(That is, that the comparator can be applied to the elements
of a, unless some bozo puts nulls there.)

/How do we sort?/

SS sort:  Bubble sort
* If you *ever* write bubble sort for one of my classes, you automatically fail
while (!unchanged) {
  unchanged = true;
  for (i = 0; i < a.length-1; i++) {
    if (c.compare(a[i],a[i+1]) > 0) {
      swap(a[i],a[i+1]);
      unchanged = false;
    }
  } // for
} // while 

O(n^2) algorithm (outerloop is O(n), inner loop is O(n))

!CK sort:
* put the first book in order
* insert the second book into the correct place relative to the first
* insert the third book into the correct place relative to the first two
* insert the fourth book into the correct place relative to the first three
...