Cod sursa(job #2898391)

Utilizator avethegamerAveTheGamer avethegamer Data 6 mai 2022 17:21:14
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;

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

void countSort(vector<int> &v, int n, int exp) {
    int output[n];
    int i, count[10] = {0};

    for (i = 0; i < n; i++)
        count[(v[i] / exp) % 10]++;

    for (i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for (i = n - 1; i >= 0; i--) {
        output[count[(v[i] / exp) % 10] - 1] = v[i];
        count[(v[i] / exp) % 10]--;
    }

    for (i = 0; i < n; i++)
        v[i] = output[i];
}

void radixsort(vector<int> &v, int n) {
    int m = *max_element(v.begin(), v.end());
    for (int exp = 1; m / exp > 0; exp *= 10)
        countSort(v, n, exp);
}

int main() {
    int N, A, B, C;
    vector<int> v;
    v.clear();
    cin >> N >> A >> B >> C;
    int x;
    v.push_back(B);
    for (int i = 2; i <= N; ++i) {
        x = (A * v[i - 1] + B) % C;
        v.push_back(x);
    }
    vector<int> w;
    w.clear();
    for (int i = 0; i < int(v.size()); i += 10) {
        w.push_back(v[i]);
    }
    radixsort(w, w.size() - 1);
    for (int i = 0; i < int(w.size()); ++i) {
        cout << w[i] << ' ';
    }
    return 0;
}