Cod sursa(job #1774734)

Utilizator nurof3nCioc Alex Andrei nurof3n Data 9 octombrie 2016 13:21:57
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;
ifstream f ("radixsort.in");
ofstream g ("radixsort.out");
const int BITS = 8;
const int MASK = (1 << BITS) - 1;
int n, a[10000001], A, B, C;
void afisare (int a[], int n)
{
    for (int i = 1; i <= n; i += 10)
        g << a[i] << ' ';
}
void selectionsort (int in, int sf)
{
    int i, j, k, tmp;
    for (i = in; i < sf; i++)
    {
        k = i;
        for (j = k + 1; j < sf; j++)
        {
            if (a[j] < a[k])
                k = j;
        }
        tmp = a[i];
        a[i] = a[k];
        a[k] = tmp;
    }
}
void radixsort (int in, int sf, int bits)
{
    int prim[1 << BITS], ultim[1 << BITS];
    for (int i = 0; i < (1 << BITS); i++)
        ultim[i] = 0;

    for (int i = in; i < sf; i++)
        ultim[ (a[i] >> bits) & MASK]++;

    prim[0] = in;
    ultim[0] += in;
    for (int i = 1; i < (1 << BITS); i++)
    {
        prim[i] = ultim[i - 1];
        ultim[i] += ultim[i - 1];
    }

    for (int i = 0; i < (1 << BITS); i++)
    {
        while (prim[i] != ultim[i])
        {
            int elem = a[prim[i]];
            int bucket = (elem >> bits) & MASK;
            while (bucket != i)
            {
                int tmp = a[prim[bucket]];
                a[prim[bucket]++] = elem;
                elem = tmp;
                bucket = (elem >> bits) & MASK;
            }
            a[prim[i]++] = elem;
        }
    }

    if (bits)
    {
        for (int i = 0; i < (1 << BITS); i++)
        {
            int lg = ultim[i] - (i ? ultim[i - 1] : in);
            if (lg > 64)
            {
                radixsort (ultim[i] - lg, ultim[i], bits - BITS);
            }
            else if (lg > 1)
            {
                selectionsort (ultim[i] - lg, ultim[i]);
            }
        }
    }
}
int main()
{
    f >> n >> A >> B >> C;
    a[1] = B;
    for (int i = 2; i <= n; i++)
    {
        a[i] = (1LL * A * a[i - 1] + B) % C;
    }
    radixsort (1, n+1, 24);
    afisare (a, n);
    return 0;
}