In [77]:

    

def counting_sort(a):
    return _counting_sort(a, max(a))

def _counting_sort(a, max_value):
    
    result = []
    counter = [0] * (max_value + 1)
    
    for i in a:
        counter[i] += 1
    
    for i, count in enumerate(counter):
        result.extend([i] * count)
    
    return result


    

In [76]:

    

d = [4,2,1,10,10,5,3,22, 7, 1]
print(counting_sort(d))


    

    




[0, 2, 1, 1, 1, 1, 0, 1, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[1, 1, 2, 3, 4, 5, 7, 10, 10, 22]

In [5]:

    

def counting_sort_in_place(a):
    """
    in-place counting sort
    http://p-nand-q.com/python/algorithms/sorting/countingsort.html
    """
    
    counter = [0] * (max(a) + 1)
    for i in a:
        counter[i] += 1
    
    pos = 0
    for i, count in enumerate(counter):
        for _ in range(count):
            a[pos] = i
            pos += 1
    return a


    

In [6]:

    

d = [4,2,1,10,10,5,3,22, 7, 1]
print(counting_sort_in_place(d))


    

    




[1, 1, 2, 3, 4, 5, 7, 10, 10, 22]

In [32]:

    

def counting_sort_alpha(a):
    max_value = 255
    
    result = []
    counter = [0] * (max_value + 1)
    
    for i in a:
        counter[ord(i)] += 1
    
    for i, count in enumerate(counter):
        result.extend([i] * count)
    
    return "".join(chr(n) for n in result)


    

In [33]:

    

d = "thisisasimplesort"
print(counting_sort_alpha(d))


    

    




aehiiilmoprsssstt

In [35]:

    

import unittest
 
class Test( unittest.TestCase ):
 
    def testCountingSortInPlace( self ):

        A = [6, 4, 3, 2, 1, 4, 3, 6, 6, 2, 4, 3, 4]
        k = 6
        counting_sort_in_place( A)
        for i in range( 1, len( A ) ):
            if A[i - 1] > A[i]:
                self.fail( "counting_sort_in_place method fails." )

    def testCountingSort( self ):

        A = [6, 4, 3, 2, 1, 4, 3, 6, 6, 2, 4, 3, 4]
        k = 6
        A = counting_sort(A)
        for i in range( 1, len( A ) ):
            if A[i - 1] > A[i]:
                self.fail( "counting_sort method fails." )
    
    def testCountingSortAlpha(self):
        A = "thisisasimplesort"
        A = counting_sort_alpha(A)
        for i in range( 1, len( A ) ):
            if ord(A[i - 1]) > ord(A[i]):
                self.fail( "counting_sort_alpha method fails." )


    

In [36]:

    

unittest.main(argv=['first-arg-is-ignored'], exit=False)


    

    




...
----------------------------------------------------------------------
Ran 3 tests in 0.003s

OK






    
Out[36]:





<unittest.main.TestProgram at 0x110e105c0>

In [38]:

    

A = [16, 4, 3, 2, 1, 4, 3, 6, 6, 2, 4, 3, 4]
import math
math.floor(math.log10(max(A))) + 1


    

    
Out[38]:





2

In [53]:

    

def get_num_difit(n):
    i = 0
    while n > 0:
        n //= 10
        i += 1
    return i


    

In [55]:

    

get_num_difit(1030)


    

    
Out[55]:





4

In [70]:

    

# source: https://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Radix_sort
import math
def radix_sort(a):
    # num_digit = math.floor(math.log10(max(a))) + 1
    num_digit = get_num_difit(max(a))
    return _radix_sort(a, num_digit)

def _radix_sort(a, num_digit):
    radix = 10
    
    for x in range(num_digit):
        bins = [[] for i in range(radix)]
        
        for y in a:
            bins[(y//radix**x)%radix].append(y)
            
        a = []
        for section in bins:
            a.extend(section)
    return a


    

In [93]:

    

# source https://www.lewuathe.com/radix-sort-in-python.html
# TODO
def get_digit(n, d):
    for i in range(d-1):
        n //= 10
    return n % 10

def get_num_difit(n):
    i = 0
    while n > 0:
        n //= 10
        i += 1
    return i

def counting_sort(a, max_value, get_index):
    counter = [0] * (max_value + 1)
    
    result = []
    for i in a:
        counter[get_index(i)] += 1
    print(counter)  
    for i, count in enumerate(counter):
            result.extend([get_index(i)] * count) 
    
    return result
def radix_sort(a):
    return _radix_sort(a, max(a))
def _radix_sort(a, max_value):
    num_digits = get_num_difit(max_value)
    
    for d in range(num_digits):
    # Counting sort takes O(n+k)
        arr = counting_sort(a, 10, lambda a: get_digit(a, d+1))
    return arr


    

In [94]:

    

A = [16, 4, 3, 42, 134, 344, 3554, 6, 26, 2, 24, 34, 124]
print(radix_sort(A))


    

    




[0, 0, 2, 1, 7, 0, 3, 0, 0, 0, 0]
[4, 1, 3, 2, 2, 1, 0, 0, 0, 0, 0]
[9, 2, 0, 1, 0, 1, 0, 0, 0, 0, 0]
[12, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

In [68]:

    

import unittest
 
class Test( unittest.TestCase ):
 
    def testRadixSort( self ):

        A = [16, 4, 3, 42, 134, 344, 3554, 6, 26, 2, 24, 34, 124]
        
        A = radix_sort(A)
        print(A)
        for i in range( 1, len( A ) ):
            if A[i - 1] > A[i]:
                self.fail( "radix_sort method fails." )


    

In [69]:

    

unittest.main(argv=['first-arg-is-ignored'], exit=False)


    

    




.





    




[2, 3, 4, 6, 16, 24, 26, 34, 42, 124, 134, 344, 3554]






    




----------------------------------------------------------------------
Ran 1 test in 0.001s

OK






    
Out[69]:





<unittest.main.TestProgram at 0x110e38ef0>

In [ ]: