Held: Friday, 9 October 2015

Back to Outline 18 - Lower Bounds. On to Outline 20 - Radix Sort.

Summary

We consider some sorting routines that achieve O(n) running time (often by limiting the input in various ways).

Related Pages

Overview

• Other strategies for sorting.
• Bucket sort.
• Radix sort.

Administrivia

• 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 Monday: Review chapter 4 of Skiena
• For next Wednesday: 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 Table Thursday: Blake

Peer

• Women's Soccer Saturday at noon.
• Men's Soccer Saturday at 2:30 p.m.
• Heavy Metal tonight at 11pm.
• YK Band 12:01 a.m. Sunday in Younker.

Other Strategies for Sorting

If we don't sort by comparing values to each other, what other options are there? That is, what tools do you have?

• Decomposing the values (strings into letters, integers into bits)
• More memory! (Hopefully O(n))
• Divide and conquer?
• ...

Bucket Sort

Suppose we only have integers between 0 and 100. What might we do?

It appears you've all thought about bucket sort.

What if our things may be different, but equal? (E.g., we could be sorting faculty by their easiness rating on RateMyProfessors.)

Is bucket sort stable?

Skienna tells us that sorting is always in Omega(nlogn). So how does it seem that we have an O(n) algorithm?

Radix Sort

What if we have a large number of 32-bit unsigned integers? We don't want to use a table of size 2^32, so what are our other options?

It turns out we can reorder them according to their bits. First we'll do the lower order bit, then the next lower-order bit, then the next lower-order bit, and so on and so forth

We'll do three bit radix sort as an example.

Is radix sort really an O(n) algorithm?