Cod sursa(job #1823402)

Utilizator AndreiFlorescuAndrei Florescu AndreiFlorescu Data 6 decembrie 2016 12:18:21
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int MASK = 255; // 2^8 - 1

vector<int> bucket[MASK + 1];
int v[10000001];

void radixSort (int k, int n) {
    int i;
    for (i = 0; i < n; i++) {
        bucket[(v[i] >> k) & MASK].push_back(v[i]);
    }
    int poz = 0;
    for (i = 0; i <= MASK; i++) {
        for (vector<int>:: iterator it = bucket[i].begin(); it != bucket[i].end(); it++) {
            v[poz++] = *it;
        }
        bucket[i].clear();
        bucket[i].resize(0);
        bucket[i].shrink_to_fit();
    }
}

int main() {
    ifstream file_in ("radixsort.in");
    ofstream file_out ("radixsort.out");

    int n, a, b, c;
    int i;

    file_in >> n >> a >> b >> c;

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

    for (i = 0; i < 4; i++) {
        radixSort(8 * i, n);
    }

    for (i = 0; i < n; i += 10) {
        file_out << v[i] << " ";
    }

    return 0;
}