Counting Sort – Explanation, Pseudocode and Implementation

Counting Sort is a linear sorting algorithm with asymptotic complexity O(n+k), which was found by Harold Seward in 1954.
Counting Sort is very time efficient and stable algorithm for sorting. Unlike bubble sort and merge sort, counting sort is not a comparison based algorithm. It avoids comparisons and exploits the O(1) time insertions and lookup in an array.

Counting Sort algorithm works on the keys that are small integer and lies between a specific range. It functions by counting the number of objects that have each distinct key value. Then it uses some arithmetic calculation to place each key value into a sorted sequence.
Its running time is O(Maximum key value – Minimum key value) which is linear. So it is useful only when a difference is not large.


Here are some key points of counting sort algorithm –

  • Counting Sort is a linear sorting algorithm.
  • Time complexity of Counting Sort is O(n+k), where n is the size of the sorted array and k is the range of key values.
  • It is not an in-place sorting algorithm as it requires extra additional space O(k).
  • Counting Sort is stable sort as relative order of elements with equal values is maintained.
  • Counting Sort is inefficient if the range of key value (k) is very large. If the input array is already sorted then also it will require an additional array to store the sorted elements and will process it completely.
  • Counting Sort has a disadvantage that it can only sort discrete values like integer, as frequency range cannot be constructed for other values.

Let’s understand it with an example –

Observe each step in the video below carefully and try to visualize the concept of this algorithm.

 


Pseudocode of Counting Sort

CountingSort(A)
  //A[]-- Initial Array to Sort
  //Complexity: O(k)
  for i = 0 to k do
  c[i] = 0

  //Storing Count of each element
  //Complexity: O(n)
  for j = 0 to n do
  c[A[j]] = c[A[j]] + 1

  // Change C[i] such that it contains actual
  //position of these elements in output array
  ////Complexity: O(k)
  for i = 1 to k do
  c[i] = c[i] + c[i-1]

  //Build Output array from C[i]
  //Complexity: O(n)
  for j = n-1 downto 0 do
  B[ c[A[j]]-1 ] = A[j]
  c[A[j]] = c[A[j]] - 1
end func

Asymptotic Analysis of Counting Sort

In this algorithm, the initialization of the count array and the loop which performs a prefix sum on the count array takes O(k) time. And other two loops for initialization of the output array takes O(n) time. Therefore, the total time complexity for the algorithm is : O(k)+ O(n)+ O(k)+ O(n)= O(n+k).

Worst Case Time complexity: O (n+k)
Average Case Time complexity: O(n+k)
Best Case Time complexity: O(n+k)
Space Complexity: O(k)
Data Structure: Array
Sorting In Place: No
Stable: Yes


Implementation of Counting Sort in C and Java programming language

C

/* C implementation Counting Sort */
#include <stdio.h>

/*  Counting sort function  */
void counting_sort(int A[], int k, int n)
{
    int i, j;
    int B[n], C[k+1];

    //Initializing counting array C[i] to 0
    for (i=0; i<=k; i++)
        C[i] = 0;
    //Store count of each element in array C
    for (j=0; j<n; j++)
        C[A[j]] = C[A[j]] + 1;

    /* Change C[i] such that it contains actual
    position of these elements in output array*/
    for (i=1; i<k+1; i++)
        C[i] = C[i] + C[i-1];

    //Creating Output array from C[i]
    //and decrementing value of C[i].
    for (j=n-1; j>=0; j--)
    {
        B[C[A[j]]-1] = A[j];
        C[A[j]] = C[A[j]] - 1;
    }

    //Printing sorted array
    printf("The Sorted array is : ");
    for (i=0; i<n; i++)
        printf("%d ", B[i]);
}

/*  The main() begins  */
int main()
{
    int n, max = 0,i;
    printf("Enter the number of input : ");
    scanf("%d", &n);
    int A[n];
    printf("\nEnter the elements to be sorted :\n");
    /*Storing element in a array.
     And finding max of elements to set range
     of counting array C[]*/
    for (i=0; i<n; i++)
    {
        scanf("%d", &A[i]);
        if (A[i] > max) {
            max= A[i];
        }
    }
    //calling counting-sort function
    counting_sort(A, max, n);
    printf("\n");
    return 0;
}

JAVA

/* Java implementation Counting Sort */
package codingeek;
import java.util.Arrays;
import java.util.Scanner;

public class CountSort {
    /*  Counting sort function  */
    void countingSort(int A[] , int max){
        int n= A.length ;
        int B[]=new int[n];
        int C[]=new int[max+1];

        //Initializing counting array C[] to 0
        for (int i=0; i <=max; i++)
            C[i] = 0;
        //Storing count of each element in array C
        for (int j=0; j<n; j++)
            C[A[j]] = C[A[j]] + 1;

        /* Change C[i] such that it contains actual
        position of these elements in output array*/
        for (int i=1; i<max+1; i++)
            C[i] = C[i] + C[i-1];

        //Creating Output array from C[i]
        //and decrementing value of C[i].
        for (int j=n-1; j>=0; j--)
        {
            B[C[A[j]]-1] = A[j];
            C[A[j]] = C[A[j]] - 1;
        }

        //Printing sorted array
        System.out.println("The Sorted array is : ");
        //print sorted array
          System.out.println(Arrays.toString(B));
    }
		
    public static void main (String args[]){
        @SuppressWarnings("resource")
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter the number of input : ");
        
        int n= sc.nextInt();
        int A[] =new int[n];
        int max=0;
        
        System.out.println("Enter the elements to be sorted :");
        
        /*Storing element in a array.
         And finding max of elements to set range
         of counting array C[]*/
        for(int i=0; i<n; i++){
            A[i]=sc.nextInt();
            if (A[i] > max) {
                max= A[i];
            }
        }

        CountSort ob= new CountSort();
        //calling counting-sort function
        ob.countingSort(A, max);

    }
}


Counting Sort is one of the most efficient and a stable algorithm for sorting. It is simple to understand and easy to implement. A good programmer must know this linear sorting algorithm. This is also a hot topic in many beginner and algorithm based interviews.
Some other Linear Sorting Algorithms are: Bucket Sort and Radix Sort.(Will be discussed in future posts)
Radix Sort can handle larger keys more efficiently as compare to Counting Sort.

Knowledge is most useful when liberated and shared. Share this to motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.

Do not forget to SHARE and SUBSCRIBE.

Keep Learning… Happy Learning.. 🙂

Recommended -