Python Program for Counting Sort

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.

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.

Example :

    
# python program for counting sort
def countingSort(inputArray):

    maxElement= max(arr)
    countArrayLength = maxElement+1
    countArray = [0] * countArrayLength

    for el in arr: 
        countArray[el] += 1

    for i in range(1, countArrayLength):
        countArray[i] += countArray[i-1] 

    outputArray = [0] * len(arr)
    i = len(arr) - 1
    while i >= 0:
        currentEl = arr[i]
        countArray[currentEl] -= 1
        newPosition = countArray[currentEl]
        outputArray[newPosition] = currentEl
        i -= 1

    return outputArray

arr = [45,22,65,78,9,23,89,52]

print("Before Sorted :: ",arr)
print("After Sorted :: ",countingSort(arr))
       

Output :

    
Before Sorted ::  [45, 22, 65, 78, 9, 23, 89, 52]
After Sorted ::  [9, 22, 23, 45, 52, 65, 78, 89]
    

The first step of the algorithm iterates over the input array n times in order to initialize the count array, so it has the complexity of O(n).

The second step iterates over the count times k times in order to calculate the cumulative sum of each element, so it has the complexity of O(k).