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.
4 | 1 | 2 | 2 | 4 | 5 | 2 |
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.
0 | 1 | 3 | 0 | 2 | 1 |
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.
0 | 1 | 4 (4-1)=3 (3-1)=2 | 4 | 6 (6-1)=5 | 7 |
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.
2 |
Taking 5
2 | 5 |
Taking 4
| | | 2 | | 4 | 5 |
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.
| | 2 | 2 | | 4 | 5 |
| 2 | 2 | 2 | | 4 | 5 |
1 | 2 | 2 | 2 | | 4 | 5 |
Taking 1
1 | 2 | 2 | 2 | 4 | 4 | 5 |
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
No, the comparison of the two elements doesn’t take place in the counting sort.
If we have a limited range of elements, then the counting sort is possible.
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.