Cod sursa(job #1496017)

Utilizator DanutsDanut Rusu Danuts Data 4 octombrie 2015 06:49:42
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");


void countsort(int v[],int n,int exp)
{
    int counts[10]={0},*output;
    output = new int[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,*v;
    fin>>n>>a>>b>>c;
    v = new int[n];
    v[0] = b;
    for(int i=1;i<n;++i)
        v[i] = (a*v[i-1]+b)%c;
    radixsort(v,n);
    for(int i=0;i<n;i+=10)
        gout<<v[i]<<" ";
    return 0;
}