Cod sursa(job #2515677)

Utilizator luliusBratu Iulian lulius Data 29 decembrie 2019 11:03:03
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
using namespace std;

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

void Vec(  int V[],  int A,  int B, int C,  int N)
{
    V[0]=B;
    for(int i=1;i<N;++i)
        V[i]=(A*V[i-1]+B)%C;
}

 int Max( int V[],int N)
{
    int max1=V[0];
    for(int i=1;i<N;++i)
        if(V[i]>max1)
            max1=V[i];
    return max1;
}

void countSort( int V[], int N, int exp)
{
    int output[N];
    int i,counT[10]={0};

    for(i=0;i<N;++i)
        counT[(V[i]/exp)%10]++;
    for(i=1;i<10;++i)
    counT[i]+=counT[i-1];

    for(i=N-1;i>=0;--i)
    {
        output[counT[(V[i]/exp)%10]-1]=V[i];
        counT[(V[i]/exp)%10]--;
    }

    for(i=0;i<N;++i)
        V[i]=output[i];
}

void Radix( int V[], int N)
{
    int m=Max(V,N);

    for(int exp=1;m/exp>0;exp*=10)
        countSort(V,N,exp);
}

int main()
{
    int N,A,B,C;
    in>>N>>A>>B>>C;
    int V[N];

    Vec(V,A,B,C,N);

    Radix(V,N);

    for(int i=0;i<N;i+=10)
        out<<V[i]<<" ";

    return 0;
}