Cod sursa(job #2623270)

Utilizator StefansenNegulescu Stefan Stefansen Data 2 iunie 2020 21:11:45
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
using namespace std;

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

void CountSort(long v[], long n, int e)
{
    int aux[n];
    int i, cnt[11] = {0};

    for(i=0;i<n;i++)
        cnt[(v[i]/e)%10]++;

    for(i=1;i<10;i++)
        cnt[i] += cnt[i-1];

    for(i=n-1;i>=0;i--)
    {
        aux[cnt[(v[i]/e)%10]-1] = v[i];
        cnt[(v[i]/e)%10]--;
    }

    for(i=0;i<n;i++)
        v[i] = aux[i];
}

void RadixSort(long v[], long n)
{
    long maxi = 0,i,e;
    for(i=1;i<=n;i++)
        if(maxi < v[i])
            maxi = v[i];


    for(e=1;maxi/e>0;e*=10)
        CountSort(v,n,e);
}

int main()
{
    long n,a,b,c,v[10000000],i;
    f>>n>>a>>b>>c;
    n++;
    v[0] = 0;
    v[1] = b;
    for(i=2;i<n;i++)
        v[i] = (a * v[i-1] + b) % c;

    RadixSort(v,n);

    for(i=1;i<n;i+=10)
        g<<v[i]<<" ";

    f.close();
    g.close();
    return 0;
}