Cod sursa(job #1248032)

Utilizator sherban26FMI Mateescu Serban-Corneliu sherban26 Data 24 octombrie 2014 15:11:38
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
//Mateescu Serban-Corneliu FMI 135
//radixsort
#include <fstream>
#include <list>

#define BASE 1
#define POW 1

using namespace std;

ifstream f ("radixsort.in");
ofstream g ("radixsort.out");

//void radix(int n, int *v, int mlen)
//{
//    list<int> bucket[BASE + 1];
//
//    for (int i = 0; i <= mlen; i += POW)
//    {
//        for (int j = 0; j < n; j++)
//            bucket[(v[j] >> i) & BASE].push_back(v[j]);
//
//        int _n = 0;
//        for (int j = 0; j <= BASE; bucket[j++].clear())
//            for (list<int>::iterator k = bucket[j].begin(); k != bucket[j].end(); v[_n++] = *(k++));
//    }
//}

int main()
{
    int n, a, b, c, m;

    f >> n;
    int v[n + 1];

    f >> a >> b >> c;

    v[0] = b;
    m = v[0];
    for (int i = 1; i < n; i++)
    {
        v[i] = (1LL * a * v[i - 1] + b) % c;
        if (m < v[i])
            m = v[i];
    }

    int mlen = 0;
    while (m)
    {
        m >>= 1;
        mlen++;
    }

    //
    //radix
    //
    int dest[n + 1];

    for (int i = 0; i < mlen; i += POW)
    {
        int bucket[BASE + 1] = {0};

        //count how much goes in each bucket
        for (int j = 0; j < n; j++)
            bucket[(v[j] >> i) & BASE]++;

        //add values to get indexes for partitioning the destination array
        for (int j = 1; j <= BASE; j++)
            bucket[j] += bucket[j - 1];

        //partition items in the dest array
        for (int j = n - 1; j >= 0; j--)
        {
            dest[--bucket[(v[j] >> i) & BASE]] = v[j];
        }

        //move items back in array v
        for (int j = 0; j < n; j++)
        {
            //cout << dest[j] << " ";
            v[j] = dest[j];
        }
    }

    //print result
    for (int i = 0; i < n; i += 10)
        g << v[i] << " ";

    return 0;
}