Cod sursa(job #1198517)

Utilizator SpiderManSimoiu Robert SpiderMan Data 15 iunie 2014 23:19:56
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>
using namespace std;

const int bytes = sizeof(int);
const int bucketSize = 32 / bytes;
const int radixSize = 1 << bucketSize;
const int mask = radixSize - 1;

int N, A, B, C;
vector<int> v;

inline int getByte(int n, int shift) {
    return (n >> shift) & mask;
}

void countSort(vector<int> &a, vector<int> &b, int byte) {
    vector<int> cnt(radixSize, 0);

    for (int i = 0; i < N; ++i)
        ++cnt[getByte(a[i], byte * bucketSize)];
    for (int i = 1; i < radixSize; ++i)
        cnt[i] += cnt[i - 1];
    for (int i = N - 1; i + 1; --i)
        b[--cnt[getByte(a[i], byte * bucketSize)]] = a[i];
}

void radixSort(vector<int> &v) {
    vector<int> aux(N, 0);
    for (int i = 0; i < 4; ++i)
        if (i & 1) {
            countSort(aux, v, i);
        } else {
            countSort(v, aux, i);
        }
}

void generateArray(vector<int> &v) {
    v.resize(N), v[0] = B;
    for (int i = 1; i < N; ++i)
        v[i] = (1LL * A * v[i - 1] + B) % C;
}

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

    f >> N >> A >> B >> C;
    generateArray(v);
    radixSort(v);
    for (int i = 0; i < N; i += 10)
        g << v[i] << " ";
}