Pagini recente » Cod sursa (job #2339144) | Cod sursa (job #840648) | Cod sursa (job #2338365) | Cod sursa (job #2427900) | Cod sursa (job #1205701)
#include <fstream>
#include <vector>
using namespace std;
void read(int& n, int& a, int& b, int& c)
{
ifstream fin("radixsort.in");
fin >> n >> a >> b >> c;
fin.close();
}
void write(const vector<int>& v)
{
ofstream fout("radixsort.out");
for (int i = 0; i < v.size(); i += 10)
fout << v[i] << ' ';
fout << '\n';
fout.close();
}
void count_sort(vector<int>& v, const int& mask, const int& rshift)
{
const int kMaxValues = (1 << 8);
int count[kMaxValues];
fill(count, count+kMaxValues, 0);
//Count how many elements belong to the bucket
for (int i = 0; i < v.size(); ++i)
++count[(v[i] & mask) >> rshift];
//Count how many elements belong to buckets <= to this one
for (int i = 1; i < kMaxValues; ++i)
count[i] += count[i - 1];
//So count of something retains the position where it should be inserted
vector<int> a(v.size());
for (int i = v.size() - 1; i >= 0; --i)
a[--count[(v[i] & mask) >> rshift]] = v[i];
v.swap(a);
}
void radix_sort(vector<int>& v)
{
const int kIntChunks = 4;
const int kByteSize = 8;
int mask = 0;
for (int i = 1; i <= kIntChunks; ++i)
{
mask = (1 << (i * kByteSize)) - mask - 1;
count_sort(v, mask, (i - 1) * kByteSize);
}
}
int main()
{
int n = 0, a = 0, b = 0, c = 1;
read(n, a, b, c);
vector<int> v;
v.push_back(b);
for (int i = 1; i < n; ++i)
v.push_back((1LL * a * v[i-1] + b) % c);
radix_sort(v);
write(v);
return 0;
}