Cod sursa(job #1841900)

Utilizator Coroian_DavidCoroian David Coroian_David Data 6 ianuarie 2017 11:27:35
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <cstdio>

#include <cstring>

#define BITS 255

using namespace std;

FILE *f, *g;

int n, a, b, c;

int v[10000003];

void readFile()
{
    f = fopen("radixsort.in", "r");

    fscanf(f, "%d%d%d%d", &n, &a, &b, &c);

    fclose(f);
}

void getNumbers()
{
    int i;

    v[1] = b;
    for(i = 2; i <= n; i ++)
        v[i] = (1LL * a * v[i - 1] % c + b) % c;
}

void radixSort()
{
    int *temp = new int[n];
    int *pozv[2] = {v, temp};
    int *aux;

    int index[BITS + 10];
    int frec[BITS + 10];
    int bits, i;

    for(bits = 0; bits < 32; bits += 8)
    {
        memset(frec, 0, sizeof(frec));

        for(i = 1; i <= n; i ++)
            frec[(pozv[0][i] >> bits) & BITS] ++;

        index[0] = 1;
        for(i = 1; i <= BITS; i ++)
            index[i] = index[i - 1] + frec[i - 1];

        for(i = 1; i <= n; i ++)
            pozv[1][index[(pozv[0][i] >> bits) & BITS] ++] = pozv[0][i];

        aux = pozv[0];
        pozv[0] = pozv[1];
        pozv[1] = aux;
    }
}

void solve()
{
    getNumbers();

    radixSort();
}

void printFile()
{
    g = fopen("radixsort..out", "w");

    int i;
    for(i = 1; i <= n; i += 10)
        fprintf(g, "%d ", v[i]);

    fprintf(g, "\n");

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}