Cod sursa(job #1240320)

Utilizator gabrieligabrieli gabrieli Data 11 octombrie 2014 00:29:22
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#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;
}