Pagini recente » Cod sursa (job #243332) | Cod sursa (job #128159) | Cod sursa (job #1043343) | Cod sursa (job #448911) | Cod sursa (job #1607288)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
const int maxn = 10000001;
int n, v[maxn], output[maxn];
int read() {
int a, b, c;
int maxim;
f >> n >> a >> b >> c;
v[0] = b%c;
maxim = v[0];
for (int i = 1; i < n; ++i) {
v[i] = (a*v[i - 1] + b) % c;
if (v[i] > maxim)
maxim = v[i];
}
return maxim;
}
void countingSort(int exp) {
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 radix(int maxim) {
for (int exp = 1; maxim / exp > 0; exp *= 10)
countingSort(exp);
}
void print() {
for (int i = 0; i < n; i += 10)
g << v[i]<<" ";
g << "\n";
}
int main()
{
radix(read());
print();
return 0;
}