#
Counting Sort In Python

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