Saturday, February 7, 2015

Radix sort in C++

#include<iostream>
#include<math.h>
using namespace std;
struct node
{
int data;
node *next;
};
void display(node *s)
{
node *p;
p=s;
cout<<"\tThus the no's are as:\n";
while(p!=NULL)
{cout<<"\t"<<p->data<<endl;
p=p->next;
}
}
node *add_end(node *q,int n)
{
node *p,*l;
l=q;
if(l==NULL)
{
l=new(node);
    l->data=n;
    l->next=NULL;
    return l;
}
else
{
while(q->next!=NULL)
    q=q->next;
      p=new(node);
    p->data=n;
        p->next=NULL;
        q->next=p;
        return l;
}

}
int main()
{
node *r[10],*l,*s,*t;
int i,n,d,k,z,j,max=-1,ctr=0;
l=new(node);
s=l;
    cout<<"Start entering the no's.....Enter -1 for aborting...\n";
    cin>>d;
    l->data=d;
    l->next=NULL;
    cin>>d;
    while(d!=-1)
     {t=new(node);
      t->data=d;
      if(max<d)
      max=d;
      t->next=NULL;
      l->next=t;
      l=t;
      cin>>d;
     }
    while(max!=0)
    {
    max=max/10;
    ctr++;
    }
    for(j=1;j<ctr+1;j++)
    {
    for(i=0;i<10;i++)
          r[i]=NULL;
    while(s!=NULL)
        {
       n=s->data;
       k=pow(10,j);
       z=n%k;
       d=pow(10,j-1);
       i=z/d;
        r[i]=add_end(r[i],n);
          s=s->next;
        }
        s=NULL;
        l=s;
        for(i=0;i<10;i++)
        {
        if(r[i]!=NULL)
        {
        t=r[i];
        if(s==NULL)
        {
        s=t;
        l=s;
        }
        else
        {
        while(s->next!=NULL)
        s=s->next;
        s->next=t;
        }
        }
        }
        s=l;
    }
    display(s);
}

No comments:

Post a Comment

Contributors

Translate