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

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.