# Counting Sort

Algo:

```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 A.length

5. 		C[A[j]] = C[A[j]] + 1

6. // C[i] now contains the number of elements equal to i .

7. for i = 1 to k

8. 		C[i] = C[i] + C[i - 1]

9. // C[i] now contains the number of elements less than or equal to i .

10.for j = A.length downto 1

11.		B[C[A[j]]] = A[j]

12.		C[A[j]] = C[A[j]] - 1```

Implemented Code:

```#include<bits/stdc++.h>
using namespace std;
void countingSort(int a[],int k,int n)
{
int i,j;
int b[15],c[100];
for(i=0;i<=k;i++)
c[i]=0;
for(j=1;j<=n;j++)
c[a[j]]=c[a[j]]+1;
for(i=1;i<=k;i++)
c[i]=c[i]+c[i-1];
for(j=n;j>=1;j--)
{
b[c[a[j]]]=a[j];
c[a[j]]=c[a[j]]-1;
}
cout<<"Sorted Array is:"<<endl;
for(i=1;i<=n;i++)
{
cout<<" ";
cout<<b[i];
}
}
int main()
{

int i,k=9; //k means maximum value in an array

int A[]={5,2,9,5,2,3,5};
int n=sizeof(A)/sizeof(A[0]);
countingSort(A,k,n);

return 0;
}
```

http://www.thecrazyprogrammer.com/2015/04/counting-sort-program-in-c.html

Tuts:

Complexity:
Time: O(k)+O(n)+O(k)+O(n)=O(n) if K=O(n)
Space: O(n)

It would be a great help, if you support by sharing :)
Author: zakilive