Cod sursa(job #1545586)

Utilizator Andrei143Andrei Andrei Andrei143 Data 6 decembrie 2015 21:05:22
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<fstream>
#include<string.h>
using namespace std;
long long n,v[10000000];
void countsort(int b,long long d[],long long s[])
{
    int c[256];
    memset(c,0,256*4);
    for (int i=0;i<n;i++)
        c[(s[i]>>(b*8))&255]++;
    for (int i=1;i<256;i++)
        c[i]+=c[i-1];
    for (int i=n-1;i>=0;i--)
        d[--c[(s[i]>>(b*8))&255]]=s[i];
}
void radixsort()
{
    long long *a=new long long[n];
    for (int i=0;i<4;i++)
        if (i%2)
        countsort(i,v,a);
        else
        countsort(i,a,v);
}
int main()
{
    ifstream f("radixsort.in");
    ofstream g("radixsort.out");
    int a,b,c;
    f>>n>>a>>b>>c;
    v[0]=b;
    for(int i=1;i<n;i++)
        v[i]=(a*v[i-1]+b)%c;
    radixsort();
    for (int i=0;i<n;i+=10)
        g<<v[i]<<" ";
    return 0;
}