CSC161 2010F, Class 37: Sorting

Overview:
* Sorting: The Six P's.
* Sorting in C.
* Some Famous Sorting Algorithms.
* Choosing a Sorting Algorithm.

Admin:
* I did not hear from anyone planning to attend today's rally, so 
  we will hold class as normal.
* Expect your next assignment late tonight or early tomorrow.
* EC for Singers Concert at 2pm on Sunday.
* EC for FreeNet meeting at 4pm on Sunday.
* EC Cool Damani Phillips concert tonight in S-L!  7:30
* Belly Dance at 3pm on Sunday (no EC)
* EC if you attend all of the Twenty-four hour improv in Younker Lounge 8pm tonight to 8pm Saturday (you must be awake for at least 20 hours of it)
* Reading for Mondaya

Sorting: 
* Given an array of values, rearrange the array so that the elements
  are organized from smallest to largest (or largest to smallest).

Procedure:
  sort
Parameters:
  a, a homogeneous array
  size, an int
  comparator, a function that lets us compare values
Purpose:
  Rearrange the array so that the elements are organized
  from smallest to largest
Produces:
  [Nothing; Called for the side effect]
Preconditions:
  size >= 0
  The array contains at least size elements
  Comparator can be applied to any two elements in a
  A = a
Postconditions:
  For all 0 <= i < size-1,
    comparator indicates that a[i] is less than a[i+1]
  a at the end is a permutation of the original
    No values were added or removed.
  A is unmodified
  a is a permutation of A

So, how do we express this in C?
* We don't yet know how to pass a function as a parameter
* We don't yet know how to say "a homogeneous array of an unknown type"

So, we might just write separate sort routines for each type
* How do we write a generic sort routine that will work for many types?

int a[]
char a[]
char *a[]

Two strategies for C programmers who want to write somewhat type-independent
code.
* Macros
#define SORTER(TYPE, COMPARE)
  void 
  sort (TYPE a[], int size) \
  { \
    if (COMPARE(a[i],a[i+1]) \
      ...
  } 
* The wonders of #include
  #define TYPE int
  #define COMPARE(x,y) x < y
  #include sort.c

sort.c

TYPE
TYPE_sort (TYPE a[], int size)
{
 ...
}

double a[]

Sorting Algorithms

* Bubble Sort - One round: Compare neighboring elements and swap
  out-of-order elements.  In each round, the largest remaining element
  "bubbles" to the end.
* Selection sort - Take the largest remaining element and swap to the
  end of the unsorted section.
  * Why use this instead of bubble sort?
    * Fewer swaps!
* Insertion sort - Two parts of the array: Unsorted part and sorted
  part.  One round: Take one element of the unsorted part and insert
  it into the appropriate place in the sorted part
* Merge sort - Split into two halves, sort the two halves, and
  merge back together
* Shell sort - We're not quite sure how it works, but it seems to
  Like insertion sort, but does the insertion using bit "steps"
* Quicksort
  Divide into small and large elements and recurse on the two
  halves.
  * Pick the "pivot" randomly