Cod sursa(job #2644638)

Utilizator DariaCretuCretu Daria Stefana DariaCretu Data 25 august 2020 13:04:40
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f ("radixsort.in");
ofstream g("radixsort.out");
int N, A, B, C,i, v[10000001];

int Maxi(int v[], int n)
{
    int maxi = v[1];
    for ( i=2; i<=n; i++ )
        if ( v[i] > maxi )
            maxi = v[i];
    return maxi;
}

void CountSort (int v[], int n, int cont)
{
    int VecFin[n], Num[10] = {0}, i;

    for ( i=0; i<n; i++ )
        Num[(v[i]/cont)%10]++;

    for ( i=1; i<=9; i++)
        Num[i] += Num[i-1];

    for ( i=n-1; i>=0; i--)
        {VecFin[Num[(v[i]/cont)%10]-1] = v[i];
         Num[(v[i]/cont)%10] --;
        }

    for (i = 0; i < n; i++)
        v[i] = VecFin[i];

}

void RadixSort (int v[], int n)
{
    int m = Maxi(v,n);
    for ( int cont=1; m/cont>0; cont*=10 )
        CountSort(v,n,cont);
}


int main()
{   f >> N >> A >> B >> C;
    v[0] = B;
    for ( i=1; i<N; i++)
        v[i] = (A * v[i-1] + B) % C;
    RadixSort(v,N);
    for (i=0; i<N; i+=10 )
        g << v[i] << " ";
    return 0;
}