%%capture
%run Counting-Sort.ipynb

"""
Explanation: Radix Sort
As <em style="color:blue">radix sort</em> is based on <em style="color:blue">counting sort</em>, 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.
End of explanation
"""


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

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

"""
Explanation: 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$.
End of explanation
"""


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

"""
Explanation: 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 <em style="color:blue">counting sort</em>.
The fact that <em style="color:blue">counting sort</em> is <em style="color:blue">stable</em> 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.
End of explanation
"""


import random as rnd

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

demo()

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

from collections import Counter

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

"""
Explanation: Testing
End of explanation
"""


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

%%time
testSort(100, 20000)

%%timeit
k = 1_000_000
L = [ rnd.randrange(2**32-1) for x in range(k) ]
S = radixSort(L)

"""
Explanation: 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.
End of explanation
"""


