Pagini recente » Cod sursa (job #457801) | Cod sursa (job #2138679) | Cod sursa (job #1906473) | Cod sursa (job #2379820) | Cod sursa (job #1240342)
#include <algorithm>
#include <fstream>
#include <iterator>
using namespace std;
//typedef unsigned long int int;
const int BASE = 128;
inline int number_of_digits(int n) {
int i;
for (i = 0; n; ++i, n /= BASE);
return i;
}
inline int get_digit(int n, int d) {
for (; d > 0; --d, n /= BASE);
return n % BASE;
}
void counting_sort(
vector<int>& v,
const int digit,
vector<int>& counter,
vector<int>& storage) {
fill(counter.begin(), counter.end(), 0);
for_each(v.begin(), v.end(), [&counter, digit] (const int& x) {
++counter[ get_digit(x, digit) ];
});
partial_sum(counter.begin(), counter.end(), counter.begin());
for_each(v.rbegin(), v.rend(), [&counter, &storage, digit] (const int& x) {
storage[ --counter[ get_digit(x, digit) ] ] = x;
});
copy(storage.begin(), storage.end(), v.begin());
}
int main() {
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
int n, a, b, c;
fin >> n >> a >> b >> c;
vector<int> v;
generate_n( back_inserter(v), n, [&a, &b, &c] () {
static int r = b % c;
int t = r;
r = ((1LL * a * r) % c + b) % c;
return t;
});
vector<int> counter(BASE);
vector<int> temp_storage(v.size());
for (int digit = 0; digit < number_of_digits(c); ++digit)
counting_sort(v, digit, counter, temp_storage);
for (int i = 0; i < v.size(); i += 10)
fout << v[i] << ' ';
fout << endl;
fout.close();
fin.close();
return 0;
}