Cod sursa(job #2551841)

Utilizator AvramDanielAvram Daniel AvramDaniel Data 20 februarie 2020 11:40:23
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include<bits/stdc++.h>
using namespace std;

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

void countsort(int t){



    for(int i = 0;i<=baza;i++){

        cnt[i] = 0;

    }



    for(int i = 0;i<n;i++){

        cnt[(v[i]/t)%baza]++;

        temp[i] = 0;

    }



    for(int i = 1;i<baza;i++){

        cnt[i]+=cnt[i-1];

    }



    for(int i = n-1;i>=0;i--){

        temp[cnt[(v[i]/t)%baza] - 1] = v[i];

        cnt[(v[i]/t)%baza]--;

    }

    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*=baza;

    }





}



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';

{1}

    cout<<mx;*/

    while(mx){

        nr_max++;

        mx/=baza;

    }

    //cout<<' '<<nr_max<<'\n';

    radixsort();



    for(int i = 0;i<n;i+=10)

        cout<<v[i]<<' ';

    return 0;

}