Cod sursa(job #240223)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 7 ianuarie 2009 00:24:30
Problema Sortare prin comparare Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
//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);
}