

In [ ]:

    
%%HTML
<style>.container { width:100% } 
</style>

Radix Sort

As radix sort is based on counting sort, we have to start our implementation of radix sort by defining the function countingSort that we have already discussed previously. The easiest way to do this is by using the %run magic that Juypter notebooks provide.



In [ ]:

    
%run Counting-Sort.ipynb

The function $\texttt{extractByte}(n, k)$ takes a natural number $n < 2^{32}$ and a number $k\in \{1,2,3,4\}$ as arguments. It returns the $k$-th byte of $n$.



In [ ]:

    
def extractByte(n, k):
    return n >> (8 * (k-1)) & 255



In [ ]:

    
n = 123456789
B = [extractByte(n, k) for k in [1, 2, 3, 4]]
assert n == sum([B[k] * 256 ** k for k in [0, 1, 2, 3]])

The function $\texttt{radixSort}(L)$ sorts a list $L$ of unsigned 32 bit integers and returns the sorted list. The idea is to sort these numbers by first sorting them with respect to their last byte, then to sort the list with respect to the second byte, then with respect to the third byte, and finally with respect to the most important byte. These four sorts are done using counting sort. The fact that counting sort is stable guarantees that when we sort with respect to the second byte, numbers that have the same second byte will still be sorted with respect to the first byte.



In [ ]:

    
def radixSort(L):
    for k in range(1, 4+1):
        Grades = [extractByte(n, k) for n in L]
        L      = countingSort(L, Grades)[0]
    return L

Testing



In [ ]:

    
import random as rnd



In [ ]:

    
def demo():
    L = [ rnd.randrange(1, 1000) for n in range(1, 16) ]
    print("L = ", L)
    S = radixSort(L)
    print("S = ", S)



In [ ]:

    
demo()



In [ ]:

    
def isOrdered(L):
    for i in range(len(L) - 1):
        assert L[i] <= L[i+1], f'L = {L}, i = {i}'



In [ ]:

    
from collections import Counter



In [ ]:

    
def sameElements(L, S):
    assert Counter(L) == Counter(S)

The function $\texttt{testSort}(n, k)$ generates $n$ random lists of length $k$, sorts them, and checks whether the output is sorted and contains the same elements as the input.



In [ ]:

    
def testSort(n, k):
    for i in range(n):
        L = [ rnd.randrange(2**31) for x in range(k) ]
        oldL = L[:]
        L = radixSort(L)
        isOrdered(L)
        sameElements(oldL, L)
        print('.', end='')
    print()
    print("All tests successful!")



In [ ]:

    
%%time
testSort(100, 20000)



In [ ]:

    
k = 1000000
L = [ rnd.randrange(2*k) for x in range(k) ]



In [ ]:

    
%%time
S = radixSort(L)



In [ ]: