CSC301.01 2015F, Class 16: Sorting
==================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* Comparing sorting algorithms.
* O(nlogn) sorting algorithms.
* Lower bounds on sorting algorithms.

Preliminaries
-------------

### Admin

### Upcoming Work

* For Monday: Work on the Exam
* For Wednesday the 16th: Exam 1 

### Extra Credit

* Don't forget that you can send these to me in advance!

#### Academic

* CS Table Tuesday at noon: NSA Barbie
* CS Extras Thursday: Blake

#### Peer

* Women's Soccer, Saturday or Sunday at 11 am
* Men's Soccer, Saturday or Sunday at 2 pm

### Exam 1

* My idiocy deleted the exam.  
        cd $(CSC301)/assignments
        pushd $(CSC151)/assignments
        cp $(CSC207)/assignments/exam.01.sect .
        EDIT EDIT EDIT
        DISCONNECT
        cd $(CSC301)/assignments
        vi exam.01.sect
        NO SUCH FILE
        cp ($CSC151)/assignments/exam01.sect .
        cd $(CSC151)/svnrepo
        svn revert exam1.2015F.sect
    * Make the exam in the 151 directory.
    * Realize the exam in the 151 directory is normally a symbolic link
      to a shared exam.
    * Copy the exam from the 151 directory to the 301 directory
    * svn revert the shared exam
    * Realize that you copied the link not the exam
* Here's a summary.  I'll rewrite tomorrow.
* Five problems.  Blind grading.
* Problem 1: Find a real algorithm with a triply-nested loop and do the
  summation analysis.
* Problem 2: For the recurrence relation T(N) <= T(2N/3) + 2T(N/3) + cN
  (a) draw the recurrence tree, (b) solve using master theorem or
  estimate using top-down or bottom-up models; (c) prove.
* Problem 3: Three proofs involving big-O notation
    * I can drop the lower order term:
      if f(n) is in O(g(n)) and h(n) is in O(f(n) + g(n)) then h(n) is in O(g(n))
    * I don't care about constant multipliers
      if f(n) is in O(c*g(n)) then f(n) is in O(g(n))
    * I can combine functions
      if f(n) is in O(g(n)) and h(n) is in O(g(n)) then
      (f(n) + h(n)) is in O(g(n))
* Problem 4: Show the correspondence between insertion in 2-3-4 trees
  and insertion in red-black trees.
* Problem 5: Merge sort with only n/2 scratch space.

### Questions

Comparing sorting algorithms
----------------------------

What kinds of things might you ask about the data set?

* Size: 
    * Will the data set fit into memory?
* Arrangement
    * Is it already mostly sorted or completely random?
* Duplicate data
    * Are there duplicate elements or are all elements distinct
* How are the data stored?
    * Array, linked list, etc.
* How will you access it later?

What kinds of things might you ask about the sorting algorithm?  (What
requirements you might have on the sorting algorithm?)

* Locality of comparisons for large data sets.
* Memory overhead
    * Quicksort: Constant; sort in place
    * Heapsort: Constant; sort in place
    * Mergesort: O(n)
* What's the asymptotic complexity?
    * Worst case
    * For the expected data
    * Average case
* What's the real running time (on your class of machine/for these data)?
* Is it stable?
    * Stable sorting routines keep "equal" values in the same order
      they were in before.

General algorithm strategy:

* Come up with a solution
* Do asymptotic analysis
* Ask if you can do better
* Repeat the above until you can't do better
* Attempt to prove that you can't do any better

O(nlogn) sorting algorithms
---------------------------

* Merge sort
    * Top-down (recursive)
    * Bottom-up (iterative)
    * Requires overhead
* Quicksort
    * Top-down (recursive)
    * Expect O(nlogn)
    * Requires luck
* Heapsort
    * Top-down (recursive)
    * No extra overhead, no luck, but weird
    * Doesn't seem faster in practice

Lower bounds on sorting algorithms
----------------------------------

Theorem: For algorithms based only on  comparing values in an array,
sorting is Omega(nlogn)

Detour: Sorting tree.  Provide a visualization of how a sorting routine
determines how to permute the array to sort it.

Any comparison-based sorting routine can be described by a sorting tree.

The best comparison-based sorting routine will require the height of the
shortest sorting tree.

How many leaves are there in a sorting tree for an array of N values (what's
the minimum number of such leaves)?  N!, the number of permutations of
N values.

Depth of tree is O(log(N!)) is approximately O(NlogN)

Lemma: 2^(N!) is in Theta(2^(NlogN))

Proof by induction