Updated April 17, 2023
Introduction to Counting Sort Python
The counting sort in python is used to sort the array by counting the number of occurrences of the each unique item in the array. Python also provides the built-in methods to sort the array. The Counting sort is one type of sorting algorithm, where it works by counting the number of unique elements occurrences in the array and finding each element’s position in the array by performing the arithmetic on those counts. The count is saved in an auxiliary array, and the sorting is accomplished by mapping the count as an index of the auxiliary array. The running time of the counting sort is linear O(n).
Algorithm of Counting Sort
The algorithm of the counting sort is given below:
Counting_Sort( a )
maxele <- maximum element in a
for i <- 0 to len(a)
In count array store the total count of each unique element at an ith index
for i <- 1 to maxele
In count array store the cumulative sum
for j <- len(a) down to 1
copy the elements to array
decrement the count of each copied element by 1Return Value:
The return value of this method is the sorted array.
Working of Counting Sort in Python
Given below is the working of counting sort in python:
1. First, determine the largest element in the specified array as max.
Given array: [3, 1, 1, 7, 2, 2, 0], max=7
2. Create an array with all elements 0 and a length of max+1. This list is used to keep track of the number of elements in the array.
Count array: [0, 0, 0, 0, 0, 0, 0, 0]
3. In the count list, store the count of each variable at its respective index.
Consider the example of element 2, whose count is 2 then, 2 is stored in the 2nd position of the count array. If element “6” is not present in the array, then 0 is stored in the 6th position.
Count of each element stored: [1, 2, 2, 1, 0, 0, 0, 1]
4. Save the total number of the count array’s elements. It aids in the placement of elements in the sorted array’s right index.
Cumulative count: [1, 3, 5, 6, 6, 6, 6, 6, 7]
5. In the count array, find the index of each member of the original array. This gives you the total number of products. Place the element at the calculated index. After each element has been placed in its proper location, reduce its count by one.
Counting sort: [0, 1, 1, 2, 2, 3, 7]
Examples of Counting Sort Python
Different examples are mentioned below:
Example #1
Example of counting sort in python to sort the array of numbers.
Code:
def counting_Sort(ary):
size = len(ary)
output = [0] * size
# create and initialize count array
count = [0] * 10
# In the count array, keep track of how many of each variable there are.
for no in range(0, size):
count[ary[no]] += 1
# Keep track of the total number of count
for no in range(1, 10):
count[no] += count[no - 1]
# In the count array, find the index of each member of the original array.
# and place the elements in output array
no = size - 1
while no >= 0:
output[count[ary[no]] - 1] = ary[no]
count[ary[no]] -= 1
no -= 1
# Copy the sorted elements into original array
for no in range(0, size):
ary[no] = output[no]
data = [ 4, 2, 4, 1, 3, 7, 9 ]
print( "The given array is: " )
print( data )
counting_Sort( data )
print( "The sorted array in ascending Order is: " )
print(data)Output:
As in the above program, the output array (store 0’s of the array size) and count array (store 0’s of the size 10) are created. Next in the count array, keep track of how many of each variable is there and store the cumulative count. Next, determine the index of each number of the original array in the count array and place them in the output array. Then finally, copy the output array that is sorted array to the passed array for printing, as we can see in the above output.
Example #2
Example for counting sort in python to sort the array of characters.
Code:
def counting_Sort(ary):
size = len(ary)
output = [0] * size
# create and initialize with 0 the count array to store
# count of each characters
count = [0 for no in range(256)]
# In the count array, keep track of how many of each variable there are.
for no in ary:
count[ord(no)] += 1
# Keep track of the total number of count
for no in range(256):
count[no] += count[no - 1]
# In the count array, find the index of each character of the original array.
# and place the elements in output array
no = size - 1
while no >= 0:
output[count[ord(ary[no])] - 1] = ary[no]
count[ord(ary[no])] -= 1
no -= 1
# Copy the sorted elements into original array
for no in range(0, size):
ary[no] = output[no]
data = [ 'a', 'f', 't', 'w' ]
print( "The given array is: " )
print( data )
counting_Sort( data )
print( "The sorted array in ascending Order is: " )
print( data )Output:
As in the above program, the output array (store 0’s of the array size) and count array (store 0’s of the size 256) are created. Next in the count array, keep track of how many of each character is there and store the cumulative count with the help of the ord() function, which returns the integer representation of the specified character. Next, determine the index of each character of the original array in the count array and place them in the output array. Then finally, copy the output array that is sorted array to the passed array for printing, as we can see in the above output.
Example #3
Example for counting sort in python to sort the characters within the given string.
Code:
def counting_Sort(ary):
size = len(ary)
output = [0] * size
# create and initialize with 0 the count array to store
# count od each characters
count = [0 for i in range(256)]
# In the count array, keep track of how many of each variable there are.
for no in ary:
count[ord(no)] += 1
# Keep track of the total number of count
for no in range(256):
count[no] += count[no - 1]
# create the string to store the resultant string
str = ["" for no in ary]
# In the count array, find the index of each character of the original array.
# and place the elements in output array
no = size - 1
while no >= 0:
output[count[ord(ary[no])] - 1] = ary[no]
count[ord(ary[no])] -= 1
no -= 1
# Copy the sorted elements into original array
for i in range(len(ary)):
str[i] = output[i]
return "".join( str )
data = "hello"
print( "The given array is: " )
print( data )
data = counting_Sort( data )
print( "The sorted array in ascending Order is: " )
print( data )Output:
As in the above program, the output array (store 0’s of the array size), count array (store 0’s of the size 256) and str (store “” of array size )are created. Next in the count array, keep track of how many of each character is there and store the cumulative count with the help of the ord () function, which returns the integer representation of the specified character. Next, determine the index of each character of the original array in the count array and place them in the output array. Then finally, copy the output array that is sorted array to the str array and joined each character of the array with the help of the join() method, which returns the string of ascending.
Conclusion
The sort string in python is used to sort the array by counting the number of occurrences of the each unique item in the array.
Recommended Articles
This is a guide to Counting Sort Python. Here we discuss the introduction, algorithm, and working of counting sort in python along with different examples and code implementation. You may also have a look at the following articles to learn more –
