Cod sursa(job #2614250)

Utilizator Razvank206Dumitriu Razvan Razvank206 Data 11 mai 2020 15:30:23
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMax 10000
using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");

int n,a,b,c,maxi,x[NMax];

void _countSort(int per)
{
    int i;
    int out[n+100];
    int cnt[12] = {0};
    for(i=1;i<=n;++i)
    {
        cnt[ (x[i]/per)%10 ]++;
    }
    for(i=1;i<10;++i)
    {
        cnt[i] += cnt[i-1];
    }
    for(i=n;i>=1;--i)
    {
        out[ cnt[ (x[i]/per)%10 ] ] = x[i];
        --cnt[ (x[i]/per)%10 ];
    }
    for(i=1;i<=n;++i)
    {
        x[i] = out[i];
    }
}

void radix_sort(int maxi)
{
    for(int per=1;per<=maxi;per*=10)
    {
        _countSort(per);
    }
}

int main()
{
    int i;
    f>>n>>a>>b>>c;
    x[1] = b;
    for(i=2;i<=n;++i)
    {
        x[i] = (a * x[i-1] + b) % c;
        if(x[i]>maxi)
            maxi = x[i];
    }
    radix_sort(maxi);
    for(i=1;i<=n;i+=10)
        g<<x[i]<<" ";
    return 0;
}