Cod sursa(job #1496020)

Utilizator DanutsDanut Rusu Danuts Data 4 octombrie 2015 07:04:14
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("radixsort.in");
ofstream gout("radixsort.out");
#define maxN 10000005
int v[maxN];

void countsort(int v[],int n,int exp)
{
    int counts[10]={0};
    int output[n];

    for(int i=0;i<n;++i)
        counts[v[i]/exp%10]++;

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

    //making the output
    for(int i=n-1;i>=0;--i){
        output[ counts[v[i]/exp%10] - 1] = v[i];
        counts[v[i]/exp%10]--;
    }

    for(int i=0;i<n;++i)
        v[i] = output[i];

}
int getMax(int v[],int n)
{
    int maxValue = v[0];
    for(int i=1;i<n;++i)
        if(maxValue < v[i])
            maxValue = v[i];
    return maxValue;
}
void radixsort(int v[],int n)
{
    int maxValue = getMax(v,n);
    for(int exp=1; maxValue/exp!=0; exp*=10)
        countsort(v,n,exp);
}
int main()
{
    int n,a,b,c;
    fin>>n>>a>>b>>c;

    v[0] = b%c;
    for(int i=1;i<n;++i)
        v[i] = (a*v[i-1]%c+b)%c;
    radixsort(v,n);
    for(int i=0;i<n;i+=10)
        gout<<v[i]<<" ";

    return 0;
}