Cod sursa(job #2619008)

Utilizator CoakazeRotaru Catalin Coakaze Data 26 mai 2020 18:30:08
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
using namespace std;

void cnt(int v[], int n, int exp)
{
    int output[n];
    int i, numara[10] = {0};
    for (i=0; i<n; i++)
        numara[(v[i]/exp)%10]++;
    for (i=1; i<10; i++)
        numara[i] += numara[i-1];
    for (i=n-1; i>=0; i--)
    {
        output[numara[(v[i]/exp)%10]-1] = v[i];
        numara[(v[i]/exp)%10]--;
    }
    for (i=0; i<n; i++)
        v[i] = output[i];
}

void radixsort(int v[], int n)
{
    int maxim = v[0];
    for (int i=1; i<n; i++)
        if (v[i] > maxim)
            maxim = v[i];
    for (int k=1; maxim/k>0; k*=10)
        cnt(v, n, k);
}

int main()
{
    ifstream f("radixsort.in");
    ofstream g("radixsort.out");
    int N, A, B, C;
    f>>N>>A>>B>>C;
    int v[100001];
    v[0]=B;
    for(int i=1; i<N; i++)
        v[i] = (A * v[i-1] + B) % C;
    radixsort(v,N);
    cout<<endl;
    for(int i=0; i<N; i=i+10)
        g<<v[i]<<" ";
    return 0;
}