CSC301.01 2015F, Class 20: Radix Sort
=====================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* A Demo.
* Thinking About Radix Sort.
* Radix Sort and Strings.
* Re-Costing Radix Sort.

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

### Admin

* Welcome to PMO, who is observing class today.
* PMO will teach the wonder of Tries on Wednesday, October 14.
* No class on Friday, October 16.
* We'll spend a few minutes going over questions on the exam.
* I've updated problem 2 so that you just have to come up with reasonable
  lower and upper bounds and show careful analysis.

### Upcoming Work

* For 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 at noon: THERAC 25

#### Peer

* SoundArt project at 7pm in Herrick

### Questions

A Demo
------

* Parallel radix sort

Thinking About Radix Sort
-------------------------

* What are the key ideas in radix sort?
    * Look at the individual bits in the integers you are sorting.
      (Generalize: Look at the individual pieces in the values you
       are sorting.)
    * You will scan through the values once per bit/position.
    * Add it to the end of the appropriate bucket for the value at 
      the position. (end keeps it stable)
* Why does it work?
    * At each round, they are ordered by the lower k bits.
* What is the running time?
    * O(p*n), where n is the number of elements and p is the number of bits
      (positions) per values
    * We might even claim that's linear time, since the number of bits
      per integer doesn't change.
* What's the space overhead?
    * O(k+n), where k represents the number of different values at each
      positiion (2 for integer radix sort)
* How would you generalize to work with strings?
    
        Assume every string is the same length.  (Pad with 0's if not.)
        for (pos = len-1; pos >= 0; pos--)a
          for (i = 0; i < n; i++)
            str = A[i]
            bucket[str[pos]].enqueue(str)
          shove everything back in A

Questions generated along the way

* Should we start with the most significant bit or the least significant bit?
    * Least significant bit to most significant
* What "sizes" do we pay attention to in computing the running time?
    * n, The number of elements we're sorting
    * k, The number of possible values
    * p, The length of each element
* Is radix sort stable?  (It's supposed to be.)

Radix Sort and Strings
----------------------

Re-Costing Radix Sort
---------------------

* For any real array (other than one at Google), log(n) < 32
* So maybe this isn't any better than an O(nlogn) algorithm.
* When we write algorithms, we are usually general: We say "for any
  size of data set", so saying that n < 2^32 is unfair.
* When we write algorithms, we don't usually pay attention to the size
  of the individual values.  When we pay attention to the size of the
  values, it should also be a parameter to your sorting routine.