Cod sursa(job #1256503)

Utilizator obidanDan Ganea obidan Data 6 noiembrie 2014 13:36:00
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <cstdio>
#include <iostream>
using namespace std;

#define BASE 256
#define NMax 10000005

int bucket[BASE];
int a[NMax],c[NMax];
int N;
void radixsort()
{
    int exp=0;
    int i,maxim=a[0];
    for(i=1;i<=N;i++)
        if(maxim<a[i])maxim=a[i];

    while(maxim>=exp)
    {
        for(i=0;i<BASE;i++)
            bucket[i]=0;
        for(i=1;i<=N;i++)
            ++bucket[(a[i]>>exp)&BASE];
        for(i=1;i<BASE;i++)
            bucket[i]+=bucket[i-1];
        for(i=N;i>0;i--)
            c[bucket[(a[i]>>exp)&BASE]--]= a[i];
        for(i=1;i<=N;i++)
            a[i]=c[i];
        exp=exp+8;
    }
}
int main()
{
    int A,B,C,i;
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    scanf("%d%d%d%d",&N,&A,&B,&C);
    a[1]=B;
    for(i=2;i<=N;i++) a[i]=(1LL*A*a[i-1]+B)%C;
    radixsort();
    for(i=1;i<=N;i=i+10)
        printf("%d ",a[i]);
}