Pagini recente » Cod sursa (job #3284437) | Cod sursa (job #2592001) | Cod sursa (job #3289634) | Cod sursa (job #152174) | Cod sursa (job #240223)
Cod sursa(job #240223)
//trie based radix sort
#include<stdio.h>
#define N 500001
struct trie { int fr;trie *b0,*b1;};
trie *root;
long n,v,i;
void readd(),prints(trie *nc,long val,long off);
int main()
{ n=(long)1<<30;
readd();
prints(root,0,(long)1<<30);
return 0;
}
void readd()
{ trie *nod,*taux;
long off_set;
root=new trie;root->b0=root->b1=0;
freopen("algsort.in","rt",stdin);
freopen("algsort.out","wt",stdout);
scanf("%ld",&n);
for(i=1;i<=n;i++)
{ scanf("%ld",&v);
nod=root;off_set=(long)1<<30;
for(;off_set;off_set>>=1)
{ if(v&off_set)
{ if(!nod->b1)
{ taux=new trie;taux->b0=0;taux->b1=0;taux->fr=0;nod->b1=taux;}
nod=nod->b1;
}
else
{ if(!nod->b0)
{ taux=new trie;taux->b0=0;taux->b1=0;taux->fr=0;nod->b0=taux;}
nod=nod->b0;
}
}
nod->fr++;
}
}
void prints( trie *nc,long val,long off)
{
if(off)
{ if(nc->b0)prints(nc->b0,val,off>>1);
if(nc->b1)prints(nc->b1,val|off,off>>1);
return;
}
for(int i=1;i<=nc->fr;i++)printf("%d ",val);
}