Cod sursa(job #1922651)

Utilizator Harsan_SabinHarsan Sabin Harsan_Sabin Data 10 martie 2017 18:16:21
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <cstring>
#define MAXI 10000000

using namespace std;

ifstream cin("radixsort.in");
ofstream cout("radixsort.out");

int n,Vec[MAXI];

int Get_Index(int x,int buck){return (x>>(8*buck))&255;}

void Counting_Sort(int *x,int *y,int n,int buck)
{
    int fv[275];

    memset(fv,0,sizeof(fv));

    for(int i=1;i<=n;++i)
        ++fv[Get_Index(x[i],buck)];

    for(int i=1;i<=255;++i)
        fv[i]+=fv[i-1];

    for(int i=n;i>0;--i)
    {
        y[fv[Get_Index(x[i],buck)]]=x[i];
        --fv[Get_Index(x[i],buck)];
    }
}

void Radix_Sort(int *Vec,int n)
{
    int *tempo = new int[n+2];

    for(int i=0;i<4;++i)
        if(i%2)
            Counting_Sort(tempo,Vec,n,i);
        else
            Counting_Sort(Vec,tempo,n,i);
}

int main()
{
    int a,b,c;

    cin>>n>>a>>b>>c;

    Vec[1]=b;
    for(int i=2;i<=n;++i)
        Vec[i]=((1LL*a*Vec[i-1])%c+1LL*b)%c;

    Radix_Sort(Vec,n);

    for(int i=1;i<=n;i+=10)
        cout<<Vec[i]<<' ';

    return 0;
}