#=======================================================================
# 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." )
