Cod sursa(job #1773916)

Utilizator nurof3nCioc Alex-Andrei nurof3n Data 8 octombrie 2016 12:56:20
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
int n, a[1000000],A,B,C;
void afisare(int a[],int n)
{
    for(int i=1;i<=n;i++)
        g<<a[i]<<' ';
}
int getmax(int a[], int n)
{
    int mx = -1000000;
    for(int i = 1; i <= n; i++)
        if(a[i] > mx) mx = a[i];
    return mx;
}
void countsort(int a[], int n, int cf)
{
    int b[n+1], ap[10] = {0};
    for(int i = 1; i <= n; i++)
        ap[(a[i] / cf) % 10]++;
    ///
    for(int i = 1; i < 10; i++)
        ap[i] += ap[i - 1];
    ///ACUM IN AP[i] SE RETINE POZITIA IN SIRUL SORTAT
    for (int i = n; i >= 1; i--)
    {
        b[ap[(a[i] / cf) % 10]] = a[i];
        ap[(a[i] / cf) % 10]--;
    }
    for (int i = 1; i <= n; i++)
        a[i] = b[i];
}
void radixsort(int a[], int n)
{
    int MAX = getmax(a, n);
    for(int cf = 1; MAX / cf > 0; cf *= 10)
        countsort(a, n, cf);
}
int main()
{
    f >> n>>A>>B>>C;
    a[1]=B;
    for(int i = 2; i <= n; i++)
    {
        a[i]=(A*a[i-1])%C;
    }
    radixsort(a, n);
    afisare(a,n);
    return 0;
}