# Counting Sort

Counting Sort: Counting sort is a sorting algorithm that is used to sort the elements of the array within a specific range. It counts the same element number of the array, and stores these same elements in the auxiliary array. It was developed by Harold H. Seward in 1954.

### Complexity table of counting sort

Where n is the number of the element, and k is the range of the input.

### Algorithm of counting sort

`Counting_Sort (array, size)  max ? find the largest element from the array.    define count array length [largest + 1].      for i ? 0 to max do       count[i] = 0 // initialize count array with all zeros.      for i ? 1 to size do       increase count of each number which has found in the array.      for i ? 1 to max do       count[i] = count[i] + count[i+1] // cumulative sum.      for i ? size to 1 decrease by 1 do       store the number in the output array.       decrease count[i]    done      return the output array End  `

Example 1: Suppose we have the following array, which we have to sort.

Step 1: Find the largest element in the given array.

Largest element is = 8   5 5 4 1 8 2 2 3

Step 2: Initialize a new array, and the size of the new array is (Largest + 1).

Step 3: Count each element in the given array, and stores the element at their respective index in the count array. For example: If 5 is assigned 2 times to the original array, then 2 will be stored at the 5th position in the count array. If 6 is assigned 0 times, then 0 will be stored at the 6th position in the count array.

Step 4: Make the cumulative sum of the elements of the count array. This helps to place the elements in the correct index of the sorted array.

Step 5:  This process will be implemented throughout the array.

Counting sort program in C language:

```  #include <stdio.h>
void countingSort(int array[], int size)
{
int output;
int max = array;
for (int i = 1; i < size; i++)
{
if (array[i] > max)      max = array[i];
}
int count;
for (int i = 0; i <= max; ++i)
{
count[i] = 0;
}
for (int i = 0; i < size; i++)
{
count[array[i]]++;
}
for (int i = 1; i <= max; i++)
{
count[i] += count[i - 1];
}
for (int i = size - 1; i >= 0; i--)
{
output[count[array[i]] - 1] = array[i];
count[array[i]]--;
}
for (int i = 0; i < size; i++)
{
array[i] = output[i];
}
}
// Function to print an array void printArray(int array[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("%d  ", array[i]);
}
printf("\n");
}   // Driver code int main()
{
int array[] = {5, 5, 4, 1, 3, 8};
int n = sizeof(array) / sizeof(array);
countingSort(array, n);
printArray(array, n);
}```