Learn How to Implement Counting Sort in Python

In this article, we will learn how to implement a counting sort in python. We will study the sorting, counting sort, time complexity, space complexity, and applications of counting sort. I’m sure at the end of the article you will get a clear idea about counting sort. Let us move on to the article.

Sorting is selecting an element one by one from a group of elements and then arranging them in either ascending or descending order. Comparison operators and sorting techniques are useful to sort elements in an array or list. Sorting plays a vital role in our day-to-day life. For example, in medical shops, medicines are arranged in alphabetical order. That is known as sorting. Some sorting techniques are Selection sort, Insertion sort, Bubble sort, Merge sort, Counting sort, etc. Now we will learn briefly about Counting sort.

What is mean by counting sort in python?

Counting sort is a type of sorting algorithm that is useful to sorts the elements of an array. It counts the number of occurrences of each unique element in an array to sort the element. The count is stored in a temp array. The sorting is done by mapping the count as an index of the temp array. Counting sort works the best when the range of numbers each value could have is very small in the array.

How does Counting sort work?

• Consider an array
• Creating an empty array
• Creating temp array
• Calculating the cumulative sum of the temp array
• Sorting

Consideration of array

Let us consider an array.

Creating Empty array

There is an array. Now we find out the maximum element in this array. So the maximum element is 5. We found the maximum element as 5, so the array’s range is definitely from 0 to 5 only. We have to create an empty array with the length of max+1.

In this empty array, we have to fill the number of occurrences of the element in its index position.

Creating temp array(temp array 1)

First, we go for 0, and there is no 0 on an array. So in an index position, 0. We have to fill 0. Next for 1, only one time one occurs. In index position 1, we have to fill 1. Next, we go for 2, two times 3 occurs. In index position 2, we have to fill 3. Next, for 3, 0 times 3 occurs. In index position 3, we have to fill 0. Likewise, it goes on.

Cumulative sum(temp array 2)

After creating a temp array, we have to create a cumulative sum. The cumulative sum is nothing but a sum of a previous and present element. In 1st position, we have 0. We can copy it as it is. In the next position, the value is 1. So the sum of 0 and 1 is 1. We have to fill 1 in the next position. The next position has a value of 3. The previous element is 1. The sum of 3 and 1 is 4. We have to fill 4 in this position. And it goes on.

The cumulative sum is 7. So we have 7 elements in an array.

Note: Before moving to sort, Please forget about temp array 1 because we modified it. Just concentrate on temp array 2

Sorting

Now we have to go for an original array. We will take the element from last.

The last element is 2. Now we have to see the 2nd position in temp array 2. The second positional value is 4 in temp array 2. Since we have to fill in order of index value. We need to do like 4-1=3, So we have to fill element 2 in the 3rd position of the new array.

Taking 5

Taking 4

The next element is 2. We have 4 in 2nd position. We all got a question there is already one element in that position. Now, what do we have to do? The solution to your question is straightforward. Just subtract it by 1. Now your value is 3. Next, we have to go for the index. Now we have to subtract again with 1. This is for index value. So we have to fill 2 in a 3rd position.

Taking 1

Finally, the array is sorted.

Pseudo code

countingsort(num):
    #Initialize an array
    #Find out the max element
    for i in range 0 to k:
        THEN do c[i] = 0
    #Find out the no of occurences
    for i in range 0 to n:
        THEN do c[num[i]]=c[num[i]]+1
    #Calculate the cumulative sum
    for j in range len(list):
        THEN do c[i] = c[i] + c[i-1]
    #Sort the array
    for j=n-1 to 0:
        THEN do res]-1]=num[i]
        c[num[i]]-=1
        i=i-1
#Input array
data=[1,7,4,8]
Bring the input data from the user and do the above calculations
print countingsort(num)

Implementing Counting Sort in Python

Example 1: Sorting Positive integers

def countingsort(num):
    n=len(num)
    res=[0]*n
    c=[0]*10
    for i in range(0,n):
        c[num[i]]=c[num[i]]+1
    for i in range(1,10):
        c[i]=c[i]+c[i-1]
    i=n-1
    while i>=0:
        res[c[num[i]]-1]=num[i]
        c[num[i]]-=1
        i=i-1
    return res
num=list(map(int,input("Enter positive numbers (give space between two numbers):").split()))
print(countingsort(num))

This is the code for sorting positive integers. It will take an array of elements from the user and sorts the elements in ascending order.

Output

Enter positive numbers (give space between two numbers):6 3 1 9 3 2 4 5 7 8
[1, 2, 3, 3, 4, 5, 6, 7, 8, 9]

Example 2: Sorting Negative Integers

def countingsort(num):
    large_element=int(max(num))
    small_element=int(min(num))
    range_elements=large_element-small_element+1
    c=[0 for a in range(range_elements)]
    n=[0 for b in range(len(num))]
    for i in range(0,len(num)):
        c[num[i]-small_element]+=1
    for i in range(1,len(c)):
        c[i]+=c[i-1]
    for i in range(len(num)-1, -1, -1):
        n[c[num[i] - small_element] - 1] = num[i]
        c[num[i] - small_element] -= 1
    for i in range(0,len(num)):
        num[i]= n[i]
    return num
num=list(map(int,input("Enter negative numbers (give space between two numbers):").split()))
print(countingsort(num))

This is the code for sorting negative integers. It will take an array of elements from the user and sorts the elements in ascending order.

Output

Enter negative numbers (give space between two numbers):-8 -5 -1 -9 -5 -3
[-9, -8, -5, -5, -3, -1]

Counting Sort in Python using the random module

import random
no_of_values= int(input("Enter how many values you want: "))
limit1= int(input("Enter a limit from where to start: "))
limit2 = int(input("Enter a limit to stop: "))
def countingsort(lst):
    for i in range(no_of_values):
            value = random.randrange(limit1,limit2)
            lst.append(value)
    a = 0
    for i in range(len(lst)):
        if lst[i] > a:
            a = lst[i]
    x = list(lst)
    y= list()
    for i in range(a):
        y.append(0)
    for j in range(0, len(lst)):
        y[lst[j]-1] += 1
    for i in range(1, a):
        y[i] += y[i-1]
    for j in range(len(lst)-1, -1, -1):
        x[y[lst[j]-1]-1] = lst[j]
        y[lst[j]-1] -= 1
    return x
lst = list()
result = countingsort(lst)
print("original list: ",lst)
print('counting sorted list: ',result)

This code is based on random numbers. It will take some random numbers in a given limit and then sort them in ascending order.

Output

Enter how many values you want: 10
Enter a limit from where to start: 1
Enter a limit to stop: 20
original list:  [17, 8, 2, 19, 3, 7, 7, 18, 18, 19]
counting sorted list:  [2, 3, 7, 7, 8, 17, 18, 18, 19, 19]

Time Complexity Of Counting Sort in python

There are four loops to sort the elements. The first loop is to find out the maximum element in the array. Second to store the no of occurrences of each element in an array. The third is for cumulative sum, and the last is to sort.

So the time complexity is O(n+k). Where n is the no of elements in an input, and k is for range.

Space Complexity Of Counting Sort in python

The space Complexity for the counting sort is O(n+k).

Applications of Counting Sort In Python

• We can sort countable objects using counting sort.
• If we have a limited range of elements, then the counting sort is possible.

FAQs related to Counting Sort in python

Conclusion

So far, we have briefly learned about counting sort in python. Counting Sort takes place in four simple steps. Finding the maximum element, counting the no of occurrences, calculating the cumulative sum, and sorting. We hope now you got a clear idea about counting sort.

In case of any queries, please communicate with us in the comment box. We will help you.

Other Sorting Algorithms You Must Look At

• Bitonic sort
• Bubble Sort
• TimSort
• Shell Sort
• Strand Sort
• Insertion Sort
• Pigeonhole Sort