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

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* Other strategies for sorting.
* Bucket sort.
* Radix sort.

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

### Admin

* PMO on Wednesday, October 14
* No class on Friday, October 16
* Grab a random number card!
* We'll spend a few minutes going over questions on the exam.

### Upcoming Work

* 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 Tuesday: THERAC-25

#### Peer

* Women's Soccer Saturday at noon.
* Men's Soccer Saturday at 2:30 p.m.
* Heavy Metal tonight at 11pm.
* TuggBoatt Bandd 12:01 a.m. Sunday in Younker.
* The Boy who Fell From the Roof, 7pm Friday, Saturday, 2:00 on Sunday

### Questions

* For problem 3: To prove that f(n) is in O(g(n)), find c, n0 s.t.  
  for all n > n0 |f(n)| <= c*|g(n)|
* Problem 1 has to be a *useful* algorithm.  The following is not useful.

        for i = 1 to n/2
                for j = 1 to i
                        for k = 1 to j
                                print "Bleh!"

* Problem 2 will require some thought (and maybe some bashing)

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

* If your data are within a limited range.
    * Create a bucket for each value within the range
    * Look at each element, and put it in the right bucket
        * If values can be distinct but equal, each bucket is a linked list
          or an array or ...
    * Pull them out of the buckets in order

Asssumptions:

* You make the buckets (an array of empty linked lists) at the beginning
* You can determine what bucket a value belongs in in constant time
* You can access that bucket in constant time
* There are n values
* There are m buckets
* A sorting algorithm is stable if, given equal values a and b, if
  a precedes b in the original array/list, a still precedes b in the
  sorted array/list

Questions

* What's the running time? O(n+m)
    * O(m) to build the array of buckets
    * O(n) to put the elements into the buckets
    * O(m+n) to get the elements out of the buckets
* Can you make this stable?  Yes, treat the linked lists as queues
* What are the associated storage requirements (in big O)?
    * O(n+m)
    * We need buckets: O(m)
    * A node for each value: O(n)
* If m is in O(n), this algorithm requires O(n) time and O(n) space
* And yes, it really is O(n), no matter what Skienna tells us

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

* Work with values in which each value is a sequence (e.g., of bits),
  in which the elements of the sequence can be ordered
* Working from the rightmost bit to the leftmost bit
     * Order the elements, keeping stable