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;
}

 

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)

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

Leave a Reply

Your email address will not be published.