Pagini recente » Cod sursa (job #2413669) | Cod sursa (job #2506934) | Cod sursa (job #1917957) | Cod sursa (job #2162350) | Cod sursa (job #2485000)
#include <fstream>
#include <vector>
#include <iostream>
void countingSort(std::vector<int>& arr, int power, int base) {
std::vector<int> count(base);
for (auto x : arr) {
++count[(x / power) % base];
}
for (int i = 1; i < base; ++i) {
count[i] += count[i - 1];
}
std::vector<int> output(arr.size());
for (int i = arr.size() - 1; i >= 0; --i) {
output[count[(arr[i] / power) % 10] - 1] = arr[i];
--count[(arr[i] / power) % 10];
}
for (int i = 0; i < arr.size(); ++i) {
arr[i] = output[i];
}
}
void radixSort(std::vector<int>& arr, int base) {
int maxn = arr[0];
for (auto x : arr) {
if (maxn < x) {
maxn = x;
}
}
for (int power = 1; power <= maxn; power *= 10) {
countingSort(arr, power, base);
}
}
int main() {
std::ifstream in("radixsort.in");
std::ofstream out("radixsort.out");
int n, a, b, c;
in >> n >> a >> b >> c;
std::vector<int> arr;
arr.push_back(b);
for (int i = 1; i < n; ++i) {
arr.push_back((a * arr[i - 1] + b) % c);
}
radixSort(arr, 10);
for (int i = 0; i < n; i += 10) {
out << arr[i] << ' ';
}
return 0;
}