Cod sursa(job #1647617)

Utilizator mateidanutDanut Gabriel Matei mateidanut Data 10 martie 2016 21:23:07
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#define NMAX 10000003
using namespace std;

int a[1000], n;

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

void Sort(int p)
{   int v[10], b[1000], i, x;
    for (i=0; i<10; ++i)
        v[i]=0;
    for (i=1; i<=n; ++i)
    {   x=(a[i]/p)%10;
        v[x]++;
    }
    for (i=1; i<10; ++i)
        v[i]+=v[i-1];
    for (i=n; i; --i)
    {   x=(a[i]/p)%10;
        b[v[x]--]=a[i];
    }
    for (i=1; i<=n; ++i)
        a[i]=b[i];
}

void Radix(int maxi)
{   for (int p=1; p<=maxi; p=p*10)
        Sort(p);
}

void Citire()
{   int v, b, c, i;
    f>>n>>v>>b>>c;
    a[1]=b;
    for (i=2; i<=n; ++i)
        a[i]=(v*a[i-1]+b)%c;
}

int main()
{   Citire();
    int i, maxi=0;
    f>>n;
    for (i=1; i<=n; ++i)
        {f>>a[i];
        maxi=max(maxi, a[i]);}
    Radix(maxi);
    for (i=1; i<=n; i++)
        g<<a[i]<<' ';
    return 0;
}