Cod sursa(job #2551613)

Utilizator AvramDanielAvram Daniel AvramDaniel Data 19 februarie 2020 23:45:24
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include<bits/stdc++.h>
using namespace std;

int a,b,c,n,v[10000010],temp[10000010], cnt[12],mx,nr_max;

void countsort(int t){

    for(int i = 0;i<=10;i++){
        cnt[i] = 0;
    }

    for(int i = 0;i<n;i++){
        cnt[(v[i]/t)%10]++;
        temp[i] = 0;
    }

    for(int i = 1;i<10;i++){
        cnt[i]+=cnt[i-1];
    }

    for(int i = n-1;i>=0;i--){
        temp[cnt[(v[i]/t)%10] - 1] = v[i];
        cnt[(v[i]/t)%10]--;
    }
    for(int i = 0;i<n;i++){
        v[i] = temp[i];
    }


}

void radixsort(){

    int exp = 1;
    for(int i = 1;i<=nr_max;i++){
        countsort(exp);
      /*  for(int j = 0;j<n;j++){
            cout<<v[j]<<' ';
        }
        cout<<'\n';*/
        exp*=10;
    }


}

int main(){

    ifstream cin("radixsort.in");
    ofstream cout("radixsort.out");
    cin>>n>>a>>b>>c;
    v[0] = b;
    mx = b;
    for(int i = 1;i<n;i++){
        v[i] = (a*v[i-1] + b)%c;
        mx = max(mx, v[i]);
    }
    /*for(int j = 0;j<n;j++){
            cout<<v[j]<<' ';
        }
        cout<<'\n';

    cout<<mx;*/
    while(mx){
        nr_max++;
        mx/=10;
    }
    //cout<<' '<<nr_max<<'\n';
    radixsort();

    for(int i = 0;i<n;i+=10)
        cout<<v[i]<<' ';
    return 0;
}