Pagini recente » Cod sursa (job #2927770) | Cod sursa (job #945483) | Cod sursa (job #434875) | Cod sursa (job #1016272) | Cod sursa (job #1240320)
#include <fstream>
#include <iterator>
#include <vector>
#include <array>
#include <algorithm>
using namespace std;
// digit = 0 is the least significant digit
size_t get_digit(size_t n, size_t digit) {
for (; digit > 0; --digit, n /= 10);
return n % 10;
}
size_t nr_digits(size_t n) {
size_t i = 0;
while (n) { ++i; n /= 10; }
return i;
}
void counting_sort(
vector<size_t>::iterator start,
vector<size_t>::iterator stop,
const size_t digit) {
vector<size_t> counter(10, 0);
vector<size_t> temp(distance(start, stop));
for_each(start, stop, [&counter, digit] (const size_t& x) {
++counter[ get_digit(x, digit) ];
});
partial_sum(counter.begin(), counter.end(), counter.begin());
reverse(start, stop);
for_each(start, stop, [&counter, &temp, digit] (const size_t& x) {
temp[ --counter[ get_digit(x, digit) ] ] = x;
});
copy(temp.begin(), temp.end(), start);
}
int main() {
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
size_t n, a, b, c;
fin >> n >> a >> b >> c;
vector<size_t> v;
generate_n( back_inserter(v), n, [&a, &b, &c] () {
static size_t r = b;
size_t t = r;
r = (a * r + b) % c;
return t;
});
for (size_t digit = 0; digit < 10; ++digit)
counting_sort(v.begin(), v.end(), digit);
for (size_t i = 0; i < v.size(); i += 10)
fout << v[i] << ' ';
fout << endl;
return 0;
}