Pagini recente » Cod sursa (job #1130777) | Cod sursa (job #1954832) | Cod sursa (job #1184184) | Cod sursa (job #1375545) | Cod sursa (job #2190351)
#include <fstream>
#include <array>
#include <queue>
std::ifstream f("radixsort.in");
std::ofstream g("radixsort.out");
int N, A, B, C;
int digits, max;
constexpr int base = 10;
std::array<int, 10000005> nums;
int GetNumOfDigits(int n)
{
int cnt = 0;
while (n) {
n /= 10;
++cnt;
}
return cnt;
}
void Generate()
{
nums[0] = B;
max = nums[0];
for (int i = 1; i < N; ++i) {
nums[i] = (A * nums[i - 1] + B) % C;
if (nums[i] > max) {
max = nums[i];
}
}
digits = GetNumOfDigits(max);
}
//void CountSort(int digit)
//{
// auto factor = [](int i) {
// int res = 1;
// for (int j = 1; j <= i; ++j)
// res *= 10;
//
// return res;
// };
//
// int i;
// int count[11] = { 0 };
// const int exp = factor(digit);
//
// for (i = 0; i < N; ++i) {
// ++count[(nums[i] / exp) % base];
// }
//
// for (i = 1; i < base; ++i) {
// count[i] += count[i - 1];
// }
//
// for (i = N - 1; i >= 0; --i) {
// nums[count[(nums[i] / exp) % base] - 1] = nums[i];
//
// }
//}
void Sort()
{
int i, j, factor;
std::queue<int> q[base];
for (i = 0, factor = 1; i < digits; ++i, factor *= base) {
for (j = 0; j < N; ++j) {
q[(nums[j] / factor) % base].emplace(nums[j]);
}
int k = 0;
for (int l = 0; l < base; ++l)
while (!q[l].empty()) {
nums[k] = q[l].front();
q[l].pop();
++k;
}
}
//for (int i = 1; i <= digits; ++i) {
// CountSort(i);
//}
}
void Print()
{
for (int i = 0; i < N; i = i + 10) {
g << nums[i] << ' ';
}
}
int main(int, char *[])
{
f >> N >> A >> B >> C;
Generate();
Sort();
Print();
return 0;
}