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

Overview

Preliminaries

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!"

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

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