Cod sursa(job #1156372)

Utilizator clopotelNeamtu Sergiu clopotel Data 27 martie 2014 16:54:45
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
int n,aa,bb,cc,v[10000002];
void afisare()
{
    for(int i=n-1; i>0; i--)
        v[i]=v[i-1];
    for(int i=1; i<=n; i+=10)
        fout<<v[i]<<" ";
}
void citire()
{
    fin>>n>>aa>>bb>>cc;
}
void generare()
{
    v[0]=bb;
    for(int i=1; i<=n; i++)
        v[i]=(aa*v[i-1]+bb)%cc;
}
void sortare()
{
    int i,b[n],m=v[1],exp=1;
    for(i=2;i<n;i++)
    {
        if(v[i]>m)
            m=v[i];
    }
    while(m/exp>0)
    {
        int bucket[10]={0};
        for(i=0;i<n;i++)
            bucket[(v[i]/exp)%10]++;
        for(i=1;i<10;i++)
            bucket[i]+=bucket[i-1];
        for(i=n-1;i>=0;i--)
            b[--bucket[(v[i]/exp)%10]]=v[i];
        for(i=0;i<=n;i++)
            v[i]=b[i];
        exp*=10;
    }
}
int main()
{
    citire();
    generare();
    sortare();
    afisare();
    return 0;
}