Python Program for Counting Sort

Counting sort is a linear-time sorting method for sorting items in an array. In this tutorial, we will sort an array with help of the counting sort operation.

Counting Sort - Basic Introduction

Counting sort is a sorting algorithm that sorts an array's items by counting the number of times each unique element appears in the array. The count is saved in an auxiliary array, and sorting is accomplished by mapping the count to an auxiliary array index. It operates by determining the number of items with unique key values (kind of hashing). Let us now have a rough understanding of how counting sort is performed:

1. Find maximum element from a given array.
2. Initialize array length with all elements 0. This will be used for sorting count elements.
3. Store count of each element with respect to their index
4. Keep track of the total sum of the count array's items.
5. In the count array, get the index of each element in the original array. This tells you the total number of items. Place the element at the computed index, as indicated in the diagram below.
6. After completing all these steps, decrease the count by 1
7. The resulting array will be sorted one.

Algorithm

As of now, we have a rough understanding of how counting sort is performed. For better understanding let's dive deep into the algorithm followed by the code:

1. Define a function Counting_Sort()
2. Pass the array parameter to the function
3. Initialize count array
4. Store count of each element in count array
5. Find the index of each element in the original array
6. Place the element in the count array
7. Copy sorted element in the count array
8. The array is sorted now
9. Print the resulting array

Program for Counting Sort(Array)

As discussed above in the algorithm, let us now dive into the programming part of the Counting Sort operation influenced by the algorithm.

def Counting_Sort(arr):
    s = len(arr)
    result = [0] * s

    # count array
    count = [0] * 10
    
    for i in range(0, s):
        count[arr[i]] += 1
        
    # cummulative count
    for i in range(1, 10):
        count[i] += count[i - 1]

    # place the elements in output array
    i = s - 1
    while i >= 0:
        result[count[arr[i]] - 1] = arr[i]
        count[arr[i]] -= 1
        i -= 1

    # Copy sorted elements 
    for i in range(0, s):
        arr[i] = result[i]

#driver code
array = [9, 8, 4, 5, 8, 9, 3, 2, 3, 1]
print("The original array is: ", array)
Counting_Sort(array)
print("Array after sorting is: ", array)

The original array is: [9, 8, 4, 5, 8, 9, 3, 2, 3, 1]
Array after sorting is: [1, 2, 3, 3, 4, 5, 8, 8, 9, 9]

Program for Counting Sort(Characters)

As we have sorted an array we can also sort characters with help of counting sort:

def Counting_Sort(array):

	result = [0 for a in range(len(array))]

	count = [0 for a in range(256)]

	# string is immutable
	answer = ["" for _ in array]

	# Store count
	for a in array:
		count[ord(a)] += 1

	for a in range(256):
		count[a] += count[a-1]

	# output character array
	for a in range(len(array)):
		result[count[ord(array[a])]-1] = array[a]
		count[ord(array[a])] -= 1

	# Copy the output array 
	for a in range(len(array)):
		answer[a] = result[a]
	return answer

# Driver program 
array = "shubhsinha"
print("The original array is:", array)
ans = Counting_Sort(array)
print("Character array after sorting is % s" %("".join(ans)))

The original array is: shubhsinha
Character array after sorting is abhhhinssu

Conclusion

In this tutorial, we have performed a Counting Sort operation in python to sort an array. Counting sort is used when there are smaller integers with multiple counts. The best-case complexity of bubble sort is O(n+k) and the space complexity of bubble sort is O(max).