Cod sursa(job #256336)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 11 februarie 2009 16:25:15
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 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-st+2;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);  
   }