Cod sursa(job #2713826)

Utilizator MateGMGozner Mate MateGM Data 28 februarie 2021 18:24:38
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb

#include <fstream>
#include <vector>
using namespace std;

int get_max(vector<int>&v,int n)
{
    int m=v[0];
    for(int i=1;i<n;i++)
        m=max(m,v[i]);
    return m;
}

void count_sort(vector<int>&v,int n,int div)
{
    vector<int>count(10,0);
    vector<int>ki(n,0);
    for(int i=0;i<n;i++)
    {
        count[(v[i]/div)%10]++;
    }
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for(int i=n-1;i>=0;i--){
        ki[count[(v[i]/div)%10]-1]=v[i];
        count[(v[i]/div)%10]--;
    }
    for(int i=0;i<n;i++)
        v[i]=ki[i];
}

void radix_sort(vector<int>&v,int n)
{
    int m=get_max(v,n);
//    cout<<m<<endl;
    for(int div=1;m/div>0;div*=10)
        count_sort(v,n,div);
}




int main()
{
    ifstream be("radixsort.in");
    ofstream ki("radixsort.out");
    int n,a,b,c;
    be>>n>>a>>b>>c;
    vector<int>v(n+1);
    v[0]=b;
    for(int i=1;i<n;i++){
        v[i]=(a*v[i-1]+b)%c;
    }
    radix_sort(v,n);
    for(int i=0;i<n;i+=10)
        ki<<v[i]<<" ";

    return 0;
}