Learn about Counting Sort in Python: How Counting Sort Works?

Introduction

Counting sort is one of the efficient sort techniques for sorting array based data(integer data). Sounds efficient because it's a non-comparison based algorithm, that means it doesn't compare any element with others for sorting. For this reason it reduce the execution time somehow(follows linear time).

The name counting because, it counts the number of occurrence of each element from the main array and store the counting result in a count array. Later it updates the main array elements on the basis of the index of that count array 

One more important thing is, this algorithm maintains the stability of the repeated element sequence while sorting. For example, there is an array like this:

arr = 4, 2, 2, 9, 1

In this case, there are two '2' digits. When the array will be sorted those two '2' digits will follow their relative order as they were in the main array. In this tutorial, you will learn how to perform Counting Sort in Python.

How does Counting Sort Work?

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

Algorithm for Counting Sort

CountingSort(array)
    size = length of array
    initialize 'temp' array; temp = [0] * size
    initialize 'count' array; count = [0] * range

    for i in range(0 to size)
        count[array[i]] = count[array[i]] + 1
   
    for i in range(1, size)
    	count[i] = count[i] + count[i-1]

    for i in range(size-1 to 0, reverse order)
        temp[count[array[i]] - 1] = array[i]
        count[array[i]] = count[array[i]] - 1

    for i in range(0 to size)
        array[i] = temp[i]

Code

'''Write a program to perform Couting Sort in Python'''
def CountingSort(array):
    size = len(array)
    # Creating an extra array to store the main array 
    # elements in the sorted order.
    temp = [0] * size

    # Initializing the count array.
    # In this case, the range of the array elements
    # from 0 to 10.
    count = [0] * 10

    # Storing the count of each element(from the main array) 
    # in the count array
    for i in range(0, size):
        count[array[i]] += 1

    # Updating the count array elements with 
    # the actual position of each element from the main array
    for i in range(1, 10):
        count[i] += count[i-1]

    # Iterate from the end(right to left) to maintain 
    # the stability of the algorithm.
    # This loop will iterate from size-1 to 0.
    for i in range(size-1, -1, -1):
        temp[count[array[i]]-1] = array[i]
        count[array[i]] -= 1

    # Copying all the elements(sorted) from temp array
    # to the main array
    for i in range(0, size):
        array[i] = temp[i]

if __name__ == "__main__":
    array = [7, 8, 2, 5, 2, 3, 1, 8]
    CountingSort(array)
    print("----Sorted Array----")
    print(array)

Output

----Sorted Array----
[1, 2, 2, 3, 5, 7, 8, 8]

Complexity Analysis

We're assuming the size or length of the array is 'n', range is 'k', and the largest number from the main array is 'max'. Now the conclusion is,

Time Complexity

Best Case: O(n+k)

Average Case: O(n+k)

Worst Case: O(n+k)

Space Complexity

For all conditions: O(max)

Drawback of Counting Sort

For example, the given array is the following:

array = [7, 8, 2, 5, 3, 2, 8, 2001]

Look at the given array; the largest element is 2001. In this case, we need to take an extra array as the same size(2001) to perform the counting sort. This is the main drawback of this sorting algorithm (If the number range is too high).