Cod sursa(job #249770)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 29 ianuarie 2009 10:46:35
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<stdio.h>
int n,i,a[500002],x[500002];
void radix(int st, int dr, int bit);
int main()
{
	freopen("algsort.in","r",stdin);
	freopen("algsort.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;++i) scanf("%d",&a[i]);
	radix(1,n,31);
	for(i=1;i<=n;i++) printf("%d ",a[i]);
	return 0;
}
void radix(int st, int dr, int bit)
{
	int s,d,b,jj,ii,st1,dr1;
	if(!bit||st==dr)return;
	s=0;d=dr+1;b=1<<(bit-1);
	for(ii=st;ii<=dr;ii++)
	{ if(a[ii]&b)x[--d]=a[ii];
	  else x[++s]=a[ii];
	}
	if(s==0||d==dr+1){ radix(st,dr,bit-1);return;}
	for(ii=1,jj=st;jj<=dr;ii++,jj++)a[jj]=x[ii];
	dr1=st+s-1;st1=dr1+1;
	radix(st,dr1,bit-1);
	radix(st1,dr,bit-1);
}