Counting Sort In Python
by Isai Damier

#=======================================================================
#  Author: Isai Damier
#  Title: Countingsort
#  Project: GeekViewpoint
#  Package: algorithms
#
#  Statement:
#  Given a disordered list of repeated integers, rearrange the
#  integers in natural order.
#
#  Sample Input: [4,3,2,1,4,3,2,4,3,4]
#
#  Sample Output: [1,2,2,3,3,3,4,4,4,4]
#
#  Time Complexity of Solution:
#  Best Case O(n+k); Average Case O(n+k); Worst Case O(n+k),
#  where n is the size of the input array and k means the
#  values range from 0 to k.
#
#  Approach:
#  Counting sort, like radix sort and bucket sort,
#  is an integer based algorithm (i.e. the values of the input
#  array are assumed to be integers). Hence counting sort is
#  among the fastest sorting algorithms around, in theory. The
#  particular distinction for counting sort is that it creates
#  a bucket for each value and keep a counter in each bucket.
#  Then each time a value is encountered in the input collection,
#  the appropriate counter is incremented. Because counting sort
#  creates a bucket for each value, an imposing restriction is
#  that the maximum value in the input array be known beforehand.
#
#  There is a great number of counting sort code on the Internet,
#  including on university websites, that erroneously claim to be
#  bucket sort. Bucket sort uses a hash function to distribute
#  values; counting sort, on the other hand, creates a counter for
#  each value -- hence the name.
#
#  Implementation notes:
#
#  1] Since the values range from 0 to k, create k+1 buckets.
#  2] To fill the buckets, iterate through the input list and
#  each time a value appears, increment the counter in its
#  bucket.
#  3] Now fill the input list with the compressed data in the
#  buckets. Each bucket's key represents a value in the
#  array. So for each bucket, from smallest key to largest,
#  add the index of the bucket to the input array and
#  decrease the counter in said bucket by one; until the
#  counter is zero.
#======================================================================= 
 def countingsort( aList, k ):
    counter = [0] * ( k + 1 )
    for i in aList:
      counter[i] += 1

    ndx = 0;
    for i in range( len( counter ) ):
      while 0 < counter[i]:
        aList[ndx] = i
        ndx += 1
        counter[i] -= 1
import unittest
from algorithms import sorting

class Test( unittest.TestCase ):

  def testCountingsort( self ):

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