Python algorithm to learn counting sort instances

Python algorithm to learn counting sort instances

# -*- coding: utf-8 -*-
def _counting_sort(A, B, k):
    """ Count sort, pseudo code is as follows: 
    COUNTING-SORT(A, B, k)
    1  for i  please  0 to k //Initializes the value of the store
    2    do C[i]  please  0
    3  for j  please  1 to length[A] //Count the values
    4    do C[A[j]]  please  C[A[j]] + 1
    5  ▷ C[i] Contains equal to i The number of elements 
    6  for i  please  1 to k //Count and determine <= the number of elements of each value
    7    do C[i]  please  C[i] + C[i-1]
    8  ▷ C[i] Contains less than or equal to i The number of elements 
    9  for j  please  length[A] downto 1
    10   do B[C[A[j]]]  please  A[j] //Put the value of A[j] in the corresponding position
    11      C[A[j]]  please  C[A[j]] - 1 //Avoid overwriting the same location at the same time
    T(n) =  Theta. (n)
    Args:
        A (Sequence):  The original array 
        B (Sequence):  The result array 
        k (int):  Value upper bound, assuming that all elements are in between [0,k]
    """
    len_c = k + 1
    C = [0] * len_c
    for a in A:
        C[a] = C[a] + 1
    for i in range(1, len_c):
        C[i] = C[i] + C[i-1]
    for a in A[::-1]:
        B[C[a]-1] = a
        C[a] = C[a] - 1
def counting_sort(A):
    """ Assume that A All the elements of the array are in between [0,len(A)-1]"""
    B = [0] * len(A)
    _counting_sort(A, B, len(A) - 1)
    return B
if __name__ == '__main__':
    import random, timeit
    items = range(10000)
    random.shuffle(items)
    def test_sorted():
        print(items)
        sorted_items = sorted(items)
        print(sorted_items)
    def test_counting_sort():
        print(items)
        sorted_items = counting_sort(items)
        print(sorted_items)
    test_methods = [test_sorted, test_counting_sort]
    for test in test_methods:
        name = test.__name__ # test.func_name
        t = timeit.Timer(name + '()', 'from __main__ import ' + name)
        print(name + ' takes time : %f' % t.timeit(1))