Counting Sort in Python (Code with Example)

In this article, we will study what is sorting and its importance. Further, we will study the counting sort and its algorithm with python code along with its output. And lastly, we will understand the time complexity of the algorithm and some important points to note while working with the counting sort algorithm. So, let’s get started!

What is Sorting?

Sorting is the process of calling the individual elements from the collection of elements and then ranking them either in ascending or descending order. As we all know programming is all about the collection of data and therefore, a sorting algorithm is used to rearrange this data in a given array or list using the comparison operator or the sorting technique. Sorting is very important in our practical life. For example, the phone numbers in phones are arranged in alphabetical order to get the result faster and efficiently. There are many Sorting Algorithms available to sort the data in an array or list and some of them are Bubble sort, Selection sort, Insertion sort, Merge sort, Counting sort, etc. In this blog, we will learn counting sort in detail with all the necessary code and example required.

What is Counting Sort Algorithm?

Counting sort is a sorting algorithm that sorts the elements with the technique of counting the number of occurrences of each unique element in an array or list. Counting algorithm is basically a hashing technique with the keys between a specific range and then counting the number of objects having distinct key values. Lastly, we will get the output sequence by doing some arithmetic calculation for positioning each object using their key values. Counting sort uses the partial hashing technique to count the occurrence of the element in O(1). The most important feature of working with counting sort is that it works with negative elements also. It uses the subroutine to another sorting algorithm. The counting sort is not a comparison-based sorting algorithm and its time complexity is O(n) with space proportional to the range of elements. Therefore, the efficiency of counting sort is maximum if the range of elements is not greater than the number of elements to be sorted. Let us study an example of counting sort for clear understanding. 

Example:

Consider a given array to be sorted. Firstly, we will find the largest element from the array and initialize it as max.

Now we will initialize the new array named count array with length “max+1” with all the elements 0 to store the sorted data.

Later, we will store elements of the given array with the corresponding index in the count array as shown in the figure. 

Now, we will modify the count array by adding the previous counts and create the cumulative sum of an array as shown below:

Since we have 7 inputs in the original array, we will create another empty array with 7 places to store the sorted data and place the elements in their correct positions and decrease the count by one.

Therefore, the sorted array is:

Algorithm for Counting Sort

countingSort(array, size)

  max <- find maximum element in the array

  initialize count array with all 0s

  for m <- 0 to size

    find the total count of each unique element and

    store the count at mth index in count array

  for n <- 1 to max

    find the cumulative sum and store it in a count array

  for m <- size down to 1

    restore the elements to the array

    decrease count of each element by 1

Python Code for Counting Sort 

# python program for counting sort

def countingSort(arr):
    size = len(arr)
    output = [0] * size

    # count array initialization
    count = [0] * 10

    # storing the count of each element 
    for m in range(0, size):
        count[arr[m]] += 1

    # storing the cumulative count
    for m in range(1, 10):
        count[m] += count[m - 1]

    # place the elements in output array after finding the index of each element of original array in count array
    m = size - 1
    while m >= 0:
        output[count[arr[m]] - 1] = arr[m]
        count[arr[m]] -= 1
        m -= 1

    for m in range(0, size):
        arr[m] = output[m]

data = [3,5,1,6,7,8,3]
countingSort(data)
print("Sorted Array: ")
print(data)

Output:

Sorted Array:

[1, 3, 3, 5, 6, 7, 8]

Time Complexity

In the above algorithm, we have 4 loops in total. The first loop to find the largest element in the given array, second to store the count of each element. Third loop stores the cumulative sum of each element in the count array and the fourth loop stores the sorted array in the new array using the indexing method of the count array.

Therefore, the overall complexity of the algorithm is O(m+n) where m is the number of elements in the input array and n is the range of input. In all the cases whether it be the best case, worst case or average case the time complexity of the algorithm is the same because the time complexity of the counting sort algorithm is not dependent on how many elements we store in the array. therefore, the time complexity of the counting sort algorithm is O(m+n). 

Applications of Counting Sort

1. Used to sort the countable objects 
2. Linear complexity is required 
3. When there are smaller integers with multiple counts possible
4. Counting sort is useful when we have a finite and limited domain of variables

Conclusion

So far, we have learned counting sort and its algorithm which sorts the elements in linear time, unlike any other sorting algorithm. Besides the linear time complexity, counting sort is very useful for finding the smaller integer with multiple counts, and therefore, it is the most preferred sorting algorithm to implement easily rather than working with any other sorting algorithms.