Cod sursa(job #2490037)

Utilizator Bogdan_BuzatuBuzatu Bogdan Mihai Bogdan_Buzatu Data 9 noiembrie 2019 16:55:52
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
int v[10000100],n,maxim,x,y,z;
void countingSort(int a[], int m, int unitate){
    int aux[10000100];
    int frecvc[10];

    for(int i=0;i<10;i++){
        frecvc[i]=0;
    }
    for(int i=0;i<m;i++){
        frecvc[(a[i]/unitate) % 10]++;
    }
    for(int i=1; i<10;i++){
        frecvc[i]+=frecvc[i-1];
    }

    for (int i = m - 1; i >= 0; i--){
        aux[frecvc[(a[i]/unitate) % 10]-1] = a[i];
        frecvc[(a[i]/unitate)%10]--;
    }

    for (int i = 0; i < m; i++){
        a[i]=aux[i];
    }

}
int main(){
    fin>>n>>x>>y>>z;

    maxim=-1;
    v[0]=y;
    maxim=max(maxim,v[0]);
    for(int i=1;i<n;i++){
        v[i]=(x*v[i-1] +y)%z;
        maxim=max(maxim,v[i]);
    }
    for(int i=1;maxim/i>0; i*=10){
        countingSort(v, n, i);
    }
    for(int i=0;i<n;i+=10){
        fout<<v[i]<<" ";
    }
}