Cod sursa(job #1758585)

Utilizator Burbon13Burbon13 Burbon13 Data 17 septembrie 2016 15:10:05
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <queue>

using namespace std;

fstream f("radixsort.in");
ofstream o("radixsort.out");

const int nmx = 10000002;
const long long galeti[] = {255, 255 << 8, 255 << 16, 1LL*255 << 24};
const int shift[] = {0,8,16,24};

int a,b,c,n;
int v[nmx];
queue <int> q[260];

void citire()
{
    f >> n >> a >> b >> c;
}

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

int place(int val, int p)
{
    return ((val &  galeti[p]) >> shift[p]);
}

void radix_sort()
{
    for(int i = 0; i < 4; ++i)
    {
        for(int j = 1; j <= n; ++j)
            q[place(v[j],i)].push(v[j]);
        v[0] = 0;
        for(int j = 0; j <= 255; ++j)
            while(not q[j].empty())
            {
                v[++v[0]] = q[j].front();
                q[j].pop();
            }

    }
}

void afish()
{
    for(int i = 1; i <= n; i += 10)
        o << v[i] << " ";
}

int main()
{
    citire();
    generare();
    radix_sort();
    afish();
    return 0;
}