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);
}
```

Code language: C++ (cpp)

#### Output:

`Sorted Array : 2 2 3 5 5 5 9`

Code language: JavaScript (javascript)

**Time and Space Complexity of Counting Sort**

Time Complexity | |

Worse Case | O(n+k) |

Best Case | O(n+k) |

Average Case | O(n+k) |

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.

Space Complexity | |

Worst Case | O(max) |

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 📧 **[email protected]**. See your articles on the main page and help other coders.😎