Friday, January 13, 2012

Counting Sort : A o(n) complexity sort

#include <stdio.h>


int b[100];
void countingsort(int a[],int b[],int k,int length);


int main()
{
//int i,a[]={2,5,3,0,2,3,0,3},b[100];
int i,a[]={1,5,20,4,2,6,19,3},b[100];
    for(int i=0;i<8;i++)
        printf("%d ",a[i]);
    printf("\n");


   countingsort(a,b,20,8);


   for(i=0;i<8;i++)
     printf("%d ",b[i]);
}


void countingsort(int a[],int b[],int k,int length)
{
int c[100],i,j;
for(i=0;i<=k;i++)
        c[i]=0;
    for(j=0;j<length;j++)
        c[a[j]]++;


    for(i=1;i<=k;i++)
        c[i]=c[i]+c[i-1];


    for(j=length-1;j>=0;j--)
    {
        b[c[a[j]]-1]=a[j];
        c[a[j]]--;
    }
}

No comments:

Post a Comment