CSC301.01 2015F, Class 18: O(n) Sorting Algorithms
==================================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* Lower bounds, revisited.
* Other techniques.
* Bucket sort.
* Radix sort.

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

### Admin

* No class on Friday, October 16
* PMO on Wednesday, October 14
* How many of you already know bucket sort and radix sort?

### Upcoming Work

* For Friday: Chapter 4 of Skiena
* For next Wednesday: [Exam 1](../assignments/exam.01.html)

### Extra Credit

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

#### Academic

* CS Table Thursday: Blake
* CS Table Tuesday at noon: Health

#### Peer

* Women's Soccer Saturday at noon against Monmouth
* Women's Soccer Saturday at 2:30 against Monmouth
* Loose Show Midnight 10/10 to 10/11
* Harry Potter FanFic Event Saturday at 3pm

### Questions

Lower bounds, revisited
-----------------------

We saw that the best we can do on a comparison-based sort was
O(log(n!)) = O(log(2^(nlogn))) = O(nlogn)

Sam gave a mediocre proof that n! =~ 2^nlogn

We're going to prove something more directly relevant

log(n!) is in Theta(nlogn)

log(n!) is in O(nlogn)

log(n!) is in Omega(nlogn)

* (1) log(n!) = log(n*(n-1)*(n-2)*...3*2*1) ; by definition
* (2) log(a*b) = log(a) + log(b) ; Lemma
* (3) log(n!) = log(n) + log(n-1) + log(n-2) + ... + log(2) + log(1) 

log(n!) is in O(nlogn)

* (4) If a > b >= 1, log(a) > log(b) >= 0 ; Def'n of log
* (5) log(n!) < log(n) + log(n) + log(n) + .... + log(n) + log(n)
* (6) log(n!) < nlog(n)
* (7) log(n!) is in O(nlogn), c = 1, n0 = 2

log(n!) is in Omega(nlogn)

* (8) log(n!) = log(n) + log(n-1) + ... log(n/2) + log(n/2-1) + ... + log(1)
* (9) log(n!) > log(n/2) + log(n/2) + ... log(n/2) + log(2) + ... + log(2) + log(1)
* (10) log(n!) > n/2*log(n/2) + n/2*(log(2))
* (11) log(n!) > n/2*(log(n)-log(2)) + n/2(log(2))
* (12) log(n!) > n/2*logn
* (13) log(n!) is in Omega(nlogn), c = 1/2 n0 = ?

Problem!  We cheated

* (14) log(n!) = log(n) + log(n-1) + ... log(n/2) + log(n/2-1) + ... + log(1)
* (15) log(n!) > n/2*log(n/2) + log(n/2-1) + log(n/2-2) + ... + log(1)
* (16) log(n!) > n/2*log(n/2) + log(n/2-1) + (n/2-2)*log(2)
* (17) log(n!) > n/2*(log(n)-log(2)) + log(n/2-1) + (n/2-2)*1
* (18) log(n!) > n/2*log(n)-n/2 + log(n/2-1) + n/2-2
* (19) log(n!) > n/2*log(n) + log(n/2-1) -2
* (20) if log(n/2-1) > 2, we're fine, n>11
* (21) log(n!) is in Omega(nlogn), c = 1/2, n0=11

Other techniques
----------------

Think about

* I'm sorting a list of 10000 integer grades, all in the range 0..100
    * Idea: If you have few distinct values and you can quickly determine
      which value it is, just put them in that "bucket" (linked list)
* I'm sorting a list of 10000 non-negative integers
    * Idea: Look at the bit representation!
* Other issues:
    * Idea: Use O(n) extra memory!  It's worth it.

Bucket sort
-----------

Radix sort
----------