# Counting Sort in C

## Counting Sort in C

Counting Sort, is an integer sorting algorithm, is a sorting technique in which we sort a collection of elements based on numeric keys between the specific range. In the counting algorithm we don’t compare element while sorting.it is often used as a subroutine in other sorting algorithm. By counting It operates the no. of objects having each distinct key value, after this it perform some arithmetic to calculate the position of each key value in output sequence.

It is used as a subroutine in another sorting algorithm for example radix sort.

If we  compare  counting sort  to bucket sort then we see that bucket sort  requires a large amount of preallocated memory or linked list and dynamic array  to hold the sets of items within each bucket, whereas counting sort instead stores a single number per bucket.

• Time complexity of counting sort is O((n). ## Algorithm of Counting Sort

Counting_Sort(A,B,K)

1-let C[0,k] be a new array
2- for i<-0 to k
3- C[i]<-0
4- for j<-1 to length[A]
5- do C[A[j]] <- C[A[j]]+1
// C[i] now contains the number of elements equal to i.
6- for i<-1 to k
7-do C[i]<- C[i]+C[i-1]
// C[i] now contains the number of elements less than or equal to i.
8- for j<- length[A] down to 1
9-do B[C[A[j]]]<- A[j]
10- C[A[j]]<-C[A[j]]-1. Execution of Counting Sort
According to algorithm let us take an example

Step 1-
i=0 to 6             since  k=6(Largest element in array A)
C[i]<-0

Step 2-
j=1 to 10            since,length[A]=10
C[A[j]]<-C[A[j]]+1

For j=1
C[A]<-C+1= 0+1 =1
C<-1

For j=2
C[A]<-C+1= 0+1 =1
C<-1

similarly for j=5,6,7,8,9,10 Step 3-
For i= 1 to 6
C[i]<-C[i]+C[i-1]

For i=1
C<-C+C
C<-1+0 = 1

For i=2
C<-C+C
C<-1+0 = 1

Similarly for i=4,5,6

Step 4-
For j=10 to 1
B[C[A[j]]]<-A[j]
C[A[j]]<-C[A[j]]-1 ### Program for Counting Sort in C

Run
```// Counting sort in C programming
#include<stdio.h>
#define MAX 255

void countSort(int array[], int size)
{
int output[MAX];
int count[MAX];
int max = array;

// Here we find the largest item in the array
for (int i = 1; i < size; i++) { if (array[i] > max)
max = array[i];
}

// Initialize the count for each element in array to 0
for (int i = 0; i <= max; ++i)
{
count[i] = 0;
}

// For each element we store the count
for (int i = 0; i < size; i++)
{
count[array[i]]++;
}

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

// Search the index of each element of the actual array in count array, and
// place the elements in output array
for (int i = size - 1; i >= 0; i--)
{
output[count[array[i]] - 1] = array[i];
count[array[i]]--;
}

// Transfer the sorted items into actual array
for (int i = 0; i < size; i++)
{
array[i] = output[i];
}
}

// printing items of the array
void display(int array[], int size)
{
for (int i = 0; i < size; i++)
printf("%d ",array[i]);
printf("\n");
}

// Driver code
int main() {
int array[] = {2, 5, 2, 8, 1, 4, 1};
int n = sizeof(array) / sizeof(array);

countSort(array, n);

display(array, n);

return 0;
}```

#### Output:

`1 1 2 2 4 5 8`

## Sorting

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews. 