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;
}
Reference:
http://scanftree.com/Data_Structure/Counting-sort
http://www.thecrazyprogrammer.com/2015/04/counting-sort-program-in-c.html
CLRS:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/countingSort.htm
Tuts:
Complexity:
Time: O(k)+O(n)+O(k)+O(n)=O(n) if K=O(n)
Space: O(n)
