Pagini recente » Cod sursa (job #2181087) | Cod sursa (job #2811728) | Cod sursa (job #3000064) | Cod sursa (job #261709) | Cod sursa (job #1759963)
#include <fstream>
#include <vector>
#include <algorithm>
#include <array>
struct file_manip {
std::ifstream fin;
std::ofstream fout;
file_manip(const char* filename) {
std::string infilename = std::string(filename) + ".in";
std::string outfilename = std::string(filename) + ".out";
fin.open(infilename.c_str());
fout.open(outfilename.c_str());
}
template <class T>
file_manip& operator << (const T& rhs) {
fout << rhs;
return *this;
}
template <class T>
file_manip& operator >> (T& rhs) {
fin >> rhs;
return *this;
}
};
int main()
{
std::vector<int> u, v;
std::array<int, 256> bucket_items;
std::array<int, 256> bucket_running_index;
int n,a,b,c;
file_manip fm("radixsort");
fm >> n >> a >> b >> c;
v.resize(n);
u.resize(n);
v[0] = b;
for (auto i = 1; i < n; ++i)
v[i] = ((v[i - 1] * a + b) % c);
for (int byte_count = 0; byte_count < 4; ++byte_count)
{
std::fill_n(bucket_items.begin(), 256, 0);
std::fill_n(bucket_running_index.begin(), 256, 0);
for (const auto i : v) {
const auto bucket = (i >> (8 * byte_count)) & 0xff;
++bucket_items[bucket];
}
for (int idx = 1; idx < 256; ++idx){
bucket_running_index[idx] = bucket_running_index[idx - 1] + bucket_items[idx - 1];
}
for (const auto i : v) {
const auto bucket = (i >> (8 * byte_count)) & 0xff;
u[bucket_running_index[bucket]++] = i;
}
v.swap(u);
}
for (auto i = 0; i < v.size(); i += 10)
fm << v[i] << " ";
return 0;
}