Cod sursa(job #2702669)

Utilizator DragosC1Dragos DragosC1 Data 5 februarie 2021 13:28:07
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <vector>
using namespace std;

int n;
vector<int> a;

void count_sort(vector<int> x, vector<int> y, int byte) {
    int i;
    int counter[256] = {0};
    int index[256];
    
    for(i = 0; i < n; i ++)
        counter[((x[i] >> (byte * 8)) & 255)]++;
    
    index[0] = 0;
    
    for(i = 1; i < 256; i ++)
        index[i] = index[i-1] + counter[i-1];
    
    for(i = 0; i < n; i ++)
        y[index[((x[i] >> (byte * 8)) & 255)]++] = x[i];
}

void radix_sort() {
    vector<int> aux;
    int i;
    for (i = 0; i < 4; i ++) {
        if(i % 2 == 0)
            count_sort(a, aux, i);
        else
            count_sort(aux, a, i);
    }
}

int main() {
    ios::sync_with_stdio(0);
    int i, x, y, z;

    ifstream f("fisier.in");
    f >> n >> x >> y >> z;
    f.close();

    a[0] = y;
    for (i = 1; i < n; i++)
        a[i] = (1LL * x * a[i - 1] + 1LL * y) % z;

    radix_sort();

    ofstream g("fisier.out");
    for (i = 0; i < n; i += 10)
        g << a[i] << ' ';
    g.close();

    return 0;
}