Cod sursa(job #2258181)

Utilizator ianiIani Biro iani Data 10 octombrie 2018 22:44:28
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>

#define NMAX 10000005

using namespace std;

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

int sir[NMAX],n,out[NMAX];

int maxsir()
{
    int maxi=sir[1];
    for (int i=2;i<=n;i++)
        if (maxi<sir[i])
            maxi=sir[i];
    return maxi;
}

void countingsort(int put)
{
    int apcif[10];
    
    for (int i=0;i<=9;i++)
        apcif[i]=0;
    
    for (int i=1;i<=n;i++)
        apcif[sir[i]/put%10]++;
    for (int i=1;i<=9;i++)
        apcif[i]+=apcif[i-1];
    for (int i=n;i>=1;i--) ///de ce scazator
    {
        out[apcif[sir[i]/put%10]]=sir[i];
        --apcif[sir[i]/put%10];
    }
    for (int i=1;i<=n;i++)
        sir[i]=out[i];
}

void radixsort()
{
    int maxi=maxsir();
    
    for (int put=1;maxi/put>0;put*=10)
        countingsort(put);
}

void afisare()
{
    for (int i=1;i<=n;i+=10)
        fout<<sir[i]<<' ';
}

int main()
{
    int a,b,c;
    fin>>n>>a>>b>>c;
    sir[1]=b;
    for (int i=2;i<=n;i++)
        sir[i]=(a * sir[i-1] + b) % c;
    radixsort();
    afisare();
    return 0;
}