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:

#### Quick Sort

Here, We will discuss about Quick sort in C, their algorithm, implementation in C, time…

#### Merge Sort

Here, We will discuss about Merge Sort in C, their algorithm, implementation code in C,…

#### Bubble Sort

Here, We will learn about bubble sort in C, their algorithm, implementation in C, time…

#### Selection Sort

Here, We will discuss about selection sort in C, their algorithm, implementation code in C,…

#### Insertion Sort

Here, We will learn about insertion sort in C, their algorithm, implementation code in C,…

#### Radix Sort

Here, We will discuss about Radix Sort in C, their algorithm, implementation code in C,…

*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.ðŸ˜Ž