Cod sursa(job #1656812)

Utilizator avaspAva Spataru avasp Data 19 martie 2016 20:23:21
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<cstdio>
#include<vector>
using namespace std;

unsigned int v[10000001],aux[10000001];

int vc[256];
int n,a,b,c,sh,cate,p8,biti;
int main(){
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    scanf("%d%d%d%d",&n,&a,&b,&c);
    v[1]=b;
    for(int i=2;i<=n;i++){
        v[i]=(a* v[i-1] + b)%c;
    }
    sh=255;
    p8=0;
    for(int q=1;q<=4;q++){
        for(int i=0;i<=255;i++)
            vc[i]=0;
        for(int i=1;i<=n;i++){
            biti=(v[i]&sh)>>p8;
            vc[biti]++;
        }

        for(int i=1;i<=255;i++)
            vc[i]+=vc[i-1];
        for(int i=255;i>=1;i--)
            vc[i]=vc[i-1];
        vc[0]=0;
        for(int i=1;i<=n;i++){
            biti=(v[i]&sh)>>p8;
            vc[biti]++;
            aux[vc[biti]]=v[i];
        }
        for(int i=1;i<=255;i++)
            v[i]=aux[i];
        //
        sh=sh<<8;
        p8+=8;
    }
    for(int i=1;i<=n;i+=10)
        printf("%d ",v[i]);
    return 0;
}