# Counting Sort

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;

//find the largest element of array
int max = arr;
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;

//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);
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

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.

### Quick Sort

Here, We will discuss about Quick sort in C, their algorithm, implementation in C, time & space complexity and their applications. What is Quick Sort? Quick …

### Merge Sort

Here, We will discuss about Merge Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. What is Merge Sort? Merge …

### Bubble Sort

Here, We will learn about bubble sort in C, their algorithm, implementation in C, time & space complexity and their applications. What is Bubble Sort? Bubble Sort …

### Selection Sort

Here, We will discuss about selection sort in C, their algorithm, implementation code in C, time and space complexity and their advantages. What is Selection Sort? Selection …

### Insertion Sort

Here, We will learn about insertion sort in C, their algorithm, implementation code in C, time and space complexity and advantages.. What is Insertion sort? Insertion Sort …

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. 