Introduction to Algorithms - Lecture 5: Linear Sorting

This post is a derivative from Introduction to Algorithms of MIT OpenCourseWare, used under CC BY-NC-SA 4.0.

You can watch this lecture on Youtube and see PDF.

Review

In a certain model of computation where I could only compare two objects, we drew a decision tree and we got the bound that, if I had n outputs, I would require my decision tree to be at least log n height. So in this model, I can’t find the things faster than log n time.

But luckily, we are in a model of computation which has a stronger operation—random accessing. If I have an item with key K and store it at index K in my array, then I can find it and manipulate it in constant time.

But, we had to instantiate a direct access array that was the size of the space of our keys.

We cam reduce the space by taking that larger key space from 0 to u, which could very large, and map it down to a small space.

If I give you a fixed hash function, that’s not going to be good in for all inputs. If your inputs are very well distributed over the key space, then it is good, but in general, there would be hash functions with some inputs that will be bad.

And so we talked about hash families, choosing a hash function randomly from among a large set of hash functions. It actually behaves really well in expectation. In particular, I got constant time for finding, inserting, and deleting into this data structure, in expectation.

But if I really can’t afford linear time ever for an operation of that kind, then I don’t want to use a hash table.

Comparison Sort Lower Bound

In the comparison model, n log(n) is optimal.

---

Direct Access Array Sort

Assume that the keys of the things you’re trying to sort out are unique and they’re in a small range. How could I use a direct access array to sort faster?

• Example: [5, 2, 7, 0, 4]
• Suppose all keys are unique non-negative integers in range {0, . . . , u − 1}, so n ≤ u
• Insert each item into a direct access array with size u in Θ(n)
• Return items in order they appear in direct access array in Θ(u)
• Running time is Θ(u), which is Θ(n) if u = Θ(n). Yay!

def direct_access_sort (A):
    "Sort A assuming items have distinct non-negative keys"
    u = 1 + max([x.key for x in A])     # O(n) find maximum key
    D = [None] * u                      # O(u) direct access array
    for x in A:                         # O(n) insert items
        D[x.key] = x
    i = 0
    for key in range (u):               # O(u) read out items in order
        if D[key] is not None:
            A[i] = D[key]
            i += 1

---

What if keys are in larger range

• What if keys are in larger range, like u = Ω(n^2) < n^2?
  • We could break this larger number into two smaller numbers.
• Idea! Represent each key k by tuple (a, b) where k = an + b
  • a = k // n
  • b = k % n
  • This is a built-in Python operation (a, b) = divmod(k, n)
• Specifically a = [k/n] < n and b = (k mod n) (just a 2-digit base-n number!)
• Example: [17, 3, 24, 22, 12] ⇒ [(3,2), (0,3), (4,4), (4,2), (2,2)] ⇒ [32, 03, 44, 42, 22](n=5)
• How can we sort tuples?

Tuple Sort

• Item keys are tuples of equal length, i.e. item x.key = (x.k1, x.k2, x.k2, . . .).
• Want to sort on all entries lexicographically, so first key k1 is most significant
• How to sort? Idea! Use other auxiliary sorting algorithms to separately sort each key
• (Like sorting rows in a spreadsheet by multiple columns)
• What order to sort them in? Least significant to most significant!
• Exercise: [32, 03, 44, 42, 22] ⇒ [42, 22, 32, 03, 44] ⇒ [03, 22, 32, 42, 44](n=5)

---

• Idea! Use tuple sort with auxiliary direct access array sort to sort tuples (a, b).
• Problem! Many integers could have the same a or b value, even if input keys distinct
• Need sort allowing repeated keys which preserves input order
• Want sort to be stable: repeated keys appear in output in same order as input
• Direct access array sort cannot even sort arrays having repeated keys!
• Can we modify direct access array sort to admit multiple keys in a way that is stable?

Counting Sort

• Instead of storing a single item at each array index, store a chain, just like hashing!
• For stability, chain data structure should remember the order in which items were added
• Use a sequence data structure which maintains insertion order
• To insert item x, insert last to end of the chain at index x.key
• Then to sort, read through all chains in sequence order, returning items one by one

def counting_sort (A):
    "Sort A assuming items have non-negative keys"
    u = 1 + max([x.key for x in A])    # O(n) find maximum key
    D = [[] for i in range(u)]         # O(u) direct access array of chains
    for x in A:                        # O(n) insert into chain at x.key
        D[x.key].append(x)
    i = 0
    for chain in D:                    # O(u) read out items in order
        for x in chain:
            A[i] = x
            i += 1

Radix Sort

We’re going to combine tuple sort and use counting sort as its auxiliary stable sorting algorithm.

Break up integers max size u into a base-n tuple. # of digit in logn(u). And then tuple sort on digits using counting sort from least to most significant.

• Idea! If u<n^2, use tuple sort with auxiliary counting sort to sort tuples (a, b)
• Sort least significant key b, then most significant key a
• Stability ensures previous sorts stay sorted
• Running time for this algorithm is O(2n)= O(n). Yay!
• If every key <n^c for some positive c = logn(u), every key has at most c digits base-n
• A c-digit number can be written as a c-element tuple in O(c) time
• We sort each of the c base-n digits in O(n) time
• So tuple sort with auxiliary counting sort runs in O(cn) time in total
• If c is constant, so each key is ≤ n^c, this sort is linear O(n)!

def radix_sort (A):
    "Sort A assuming items have non-negative keys"
    n = len(A)
    u = 1 + max([x.key for x in A])               # O(n) find maximum key
    c = 1 + (u.bit_length() // n.bit_length())
    class obj: pass
    D = [obj() for a in A]
    for i in range(n):                            # O(nc) make digit tuples
        D[i].digits = []
        D[i].item = A[i]
        high = A[i].key
        for j in range(c):                        # O(c) make digit tuple
            high, low = divmod(high, n)
            D[i].digits.append(low)
    for i in range(c):                            # O(nc) sort each digit
        for j in range(n):                        # O(n) assign key i to tuples
            D[j].key = D[j].digits[i]
        counting_sort(D)                          # O(n) sort on digit i
    for i in range(n):                            # O(n) output to A
        A[i] = D[i].item

Algorithm	Time O(·)	In-place?	Stable?	Comments
Insertion Sort	n^2	Y	Y	O(nk) for k-proximate
Selection Sort	n^2	Y	N	O(n) swaps
Merge Sort	n log n	N	Y	Stable, optimal comparison
Counting Sort	n + u	N	Y	O(n) when u = O(n)
Radix Sort	n + n logn(u)	N	Y	O(n) when u = O(n^c)