Counting Sort

Last updated on September 4th, 2023 at 09:44 pm

Here, We will discuss about Counting Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications.

What is Counting Sort?

Counting Sort is a sorting algorithm but not a comparison sort algorithm.

The algorithm based on idea that sorting the elements of an array by frequencies of distinct/unique elements of the array.

Counting Sort becomes linear sorting which is better than comparison based sorting algorithm.

Counting Sort Algorithm

Sorting of elements of an array by frequencies of distinct elements of array. The count is stored in auxiliary array and the sorting is done by mapping its value as an index of the auxiliary array.

Counting Sort Code Implementation

Program code in C

#include<stdio.h>

void countingsort(int arr[], int n)
{
  int output[10];

  //find the largest element of array
  int max = arr[0];
  for(int i=1; i<n; i++)
  {
    if(arr[i] > max)
      max = arr[i];
  }

  //the size of count must be at least (max+1)
  int count[10];
  
  //Initialize count array with all zeros.
  for(int i=0; i<=max; i++)
  {
    count[i] = 0;
  }

  //store the count of each element
  for(int i=0; i<n; i++)
  {
    count[arr[i]]++;
  }

  //store the cummulative count of each array
  for(int i=1; i<=max; i++)
  {
    count[i] += count[i-1];
  }

  //find index of each elements of original array in count array and
  //place the elements in output array
  for(int i=n-1; i>=0; i--)
  {
    output[count[arr[i]]-1] = arr[i];
    count[arr[i]]--;
  }

  //copy the sorted elements into original array
  for(int i=0; i<n; i++)
  {
    arr[i] = output[i];
  }
}

//function to print array
void printarray(int arr[], int n)
{
  for(int i=0; i<n; i++)
  {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

//Driver code
int main()
{
  int data[] = {5, 2, 9, 5, 2, 3, 5};
  int n = sizeof(data) / sizeof(data[0]);
  countingsort(data, n);
  printf("Sorted Array : ")
  printarray(data, n);
}

Output:

Sorted Array : 2 2 3 5 5 5 9

Time and Space Complexity of Counting Sort

In all cases, the complexity is the same because no matter how the elements are placed in the array, the algorithm goes through (n+k) times.

Larger the range of elements, larger is the space complexity.

Applications of Counting Sort

Counting Sort is used when:

• there are smaller integers with multiple counts.
• linear complexity is the need.

Related:

Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to 📧 contribute@totheinnovation.com. See your articles on the main page and help other coders.😎