Cod sursa(job #2614123)

Utilizator hirneagabrielHirnea Gabriel hirneagabriel Data 11 mai 2020 11:48:33
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <cmath>

#define N 100000000
int v[N];
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

int Max(int n)
{
    int Max = v[0];
    for (int i = 1; i < n; i++)
        if (v[i] > Max)
            Max = v[i];
    return Max;
}
void countSort(int n, int poz, int baza) {
    int a[n+1];
    int i, b[baza] = { 0 };
    for (i = 0; i < n; i++)
        b[(v[i] / int(pow(double(baza),double(poz))))%baza]++;
    for (i = 1; i < baza; i++)
        b[i] += b[i-1];
    for (i = n - 1; i >= 0; i--)
    {
        a[b[(v[i] / int(pow(double(baza),double(poz))))%baza]-1] = v[i];

        b[(v[i] / int(pow(double(baza),double(poz))))%baza]--;
    }
    for (i = 0; i < n; i++)
        v[i] = a[i];
}
void radixsort(int n,int baza)
{   int nrcifre;
    int m = Max(n);
    nrcifre = int(log(m) / log(baza)+1);

    for (int poz = 0; poz< nrcifre; poz ++)
        countSort(n,poz,baza);

}

int main()
{
    int n,A,B,C;
    fin >> n>>A>>B>>C;
    v[0]=B;
    for (int i = 1; i < n; i++)
        v[i]=(A * v[i-1] + B) % C;
    radixsort(n,C);
    for (int i = 0; i < n; i+=10)
        fout << v[i] << " ";
    return 0;
    return 0;
}