Cod sursa(job #2626139)

Utilizator miramaria27Stroie Mira miramaria27 Data 6 iunie 2020 12:07:38
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("radixsort.in");
ofstream out("radixsort.out");

vector<int> a, result;

void counting(int times, int n)
{
    int nr[16]= {0};
    for(long long i=0; i<n; i++)
    {
        int cifra=(a[i]>>times)& 15;
        nr[cifra]++;
    }
    for(int i=1; i<16; i++)
        nr[i]+=nr[i-1];

    for(int i=n-1; i>=0; i--)
    {
        int cifra=(a[i]>>times)&15;
        result[nr[cifra]-1]=a[i];
        nr[cifra]--;
    }
    for(int i=0;i<n;i++)
        a[i]=result[i];

}
void radixsort( int n)
{
    int ma=*max_element(a.begin(),a.end());
    int times=0;
    while((ma>>times)>0)
    {

        counting(times,n);
        times+=4;

    }
}
int main()
{
    int N,A,B,C;
    in>>N>>A>>B>>C;
    a.reserve(10000001);
    result.reserve(10000001);
    a[0]=B;
    for(int i=1; i<N; i++)
        a[i]=(A*a[i-1]+B)%C;
    radixsort(N);
    for(int i=0; i<N; i+=10)
        out<<a[i]<<" ";
    return 0;
}