How to implement Counting Sort Algorithm Python

In this tutorial, we’ll learn about counting sort algorithm in Python.

Counting sort is a stable sorting algorithm, which uses the frequencies of each element in the array to sort the given array in linear time. However, it is efficient only when the range of the input data is not much greater than the number of elements in the input array.

Counting Sort Algorithm

This algorithm sorts a list of objects by mapping the number of occurrences of each distinct object to the object’s value (using a count array).

Say, we’re given an array of integers size ‘n’ whose maximum element is ‘max’.

Construct a count array of size max+1, where, count[i] is the number of times i occurs in the input array arr.
Update the count array, so that each element in the array stores the cumulative count at that index. i.e., count[i] = ∑count[k] where 0<=k<=i.
Now, for an integer i, count[i] is the number of elements less than or equal to i in the array arr. So, what does this number say? It represents the last position that, that item can occur in the output array. i.e., for a given i, count[i] is the last position where i can occur in res.
Iterate through the input array arr, for each element arr[i], fill the output array as output[count[arr[i]]-1]=arr[i] and decrement count[arr[i]] by one.
The resulting output array is the sorted sequence.

Python Solution

def countingSort(arr):
    
    count = [0]*(max(arr)+1)
    res = [0]*len(arr)
    for num in  arr:
        count[num] = count[num]+1
    for i in range(1,len(count)):
        count[i] = count[i-1]+count[i]
    for num in arr:
        res[count[num]-1] = num
        count[num] = count[num]-1
    print("The sorted array is ", res)
    return

if __name__ == "__main__":
  arr = [5,2,4,2,1,5,1,5]
  countingSort(arr)

Output:

The sorted array is  [1, 1, 2, 2, 4, 5, 5, 5]

Java Solution

import java.util.*;
import java.io.*;

public class countingSort
{
  public static void main(String[] args)
  {
    int arr[] = {5,2,4,2,1,5,1,5};
    int n = arr.length, max;
    int res[] = new int[n];

    //finding maximum element in the array
    max = arr[0];
    for(int i=0;i<n;i++)
      max = (arr[i]>max) ? (arr[i]) : (max);

    //count array and cumulative count
    int count[] = new int[max+1];
    for(int i=0;i<n;i++)
      count[arr[i]]++;
    for(int i=1;i<count.length;i++)
      count[i] = count[i]+count[i-1];

    //filling the result array
    for(int i=0;i<n;i++)
    {
      res[count[arr[i]]-1] = arr[i];
      count[arr[i]]--;
    }

    //printing the result
    for(int i=0;i<n;i++)
      System.out.print(res[i]+" ");
  }
}

Output

1 1 2 2 4 5 5 5

Complexity Analysis

Time complexity : O(n+max) (O(n) for iterating through the input, result array and O(max) for iterating through the count array)

Space complexity : O(max) Therefore, larger the range of elements, larger is the space complexity.

It can be seen that counting sort runs in almost linear time unlike the comparison-based sorting algorithms like the bubble sort, quick sort etc and proves to be the most efficient choice to sort a set of objects when the range of the input data is not much greater than the number of items to be sorted.

The above algorithm can be further extended to sort an array with negative numbers by mapping the least negative number to the 0th index in the count array.

Taking it further

So, we’ve learnt that counting sort can sort an array efficiently in linear time, unlike the comparison-based sorting algorithms which can give a best-case time complexity of O(n logn). So, what if, you’re given an array, whose length is n, and it’s elements range from 1 to n²?? Will it be a wise choice to go for counting sort now??

NO! In such a case, counting sort performs with time complexity of O(n²) (worse than comparison based sorting algo).. So, is there no way to sort such an array in linear time?

In such a case, radix sort comes to the rescue. It is interesting to note that, Radix sort, in turn, uses counting sort as a subroutine to sort.

References:

Happy Learning 🙂