Cod sursa(job #2614210)

Utilizator mihaimbMihai Badea mihaimb Data 11 mai 2020 14:32:05
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

int maxelem(std::vector<int> vec)
{
    int rez = vec[0];

    for(int i=1; i<vec.size(); i++)
    {
        if(vec[i]>rez) rez = vec[i];
    }

    return rez;
}

std::vector<int> cntdig(std::vector<int> vec, int exp)
{
    std::vector<int> rez(vec.size());

    int H[10] = { };

    for(int i=0; i<vec.size(); i++)
    {
        H[(vec[i]/exp)%10]++;
    }

    for(int i=1; i<10; i++)
    {
        H[i]=H[i]+H[i-1];
    }

    for(int i=vec.size()-1; i>=0; i--)
    {
        rez[H[(vec[i]/exp)%10] -1]=vec[i];
        H[(vec[i]/exp)%10]--;
    }

    return rez;
}

std::vector<int> radix(std::vector<int> vec)
{
    int m=maxelem(vec), exp=1;

    while(m>0)
    {
        vec=cntdig(vec, exp);
        m=m/10;
        exp=exp*10;
    }

    return vec;
}


int main()
{

    int n,a,b,c;

    std::vector<int> v;

    v.reserve(10000000);

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

    fin>>n>>a>>b>>c;

    v.push_back(b);

    for(int i=1; i<n; i++)
    {
        v.push_back((a*v[i-1] + b) % c);
    }

    v=radix(v);

    for(int i=0; i<n; i+=10)
    {
        fout<<v[i]<<' ';
    }

    fout<<'\n';


    return 0;
}