Cod sursa(job #1156010)

Utilizator rockerboyHutter Vince rockerboy Data 27 martie 2014 12:46:17
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <vector>

using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");

typedef vector<int> Vektor;
typedef vector<int>::iterator Iterator;
typedef vector<int>::const_iterator cIterator;

int szamjegy(int minek, int hanyadik)
{
    --hanyadik;
    while (hanyadik)
    {
        minek /= 10;
        --hanyadik;
    }
    return minek%10;
}

void radix_sort (Vektor& x)
{
    vector< vector<int> > temp1(10);
    int j, i, szj;
    for (Iterator it=x.begin(); it<x.end(); it++)
    {
        szj = szamjegy(*it, 1);
        temp1[szj].push_back(*it);
    }

    i = 2;
    int n = x.size();

    while (i != n+1)
    {
        vector< vector<int> > temp2(10);
        for (j=0; j<10; j++)
        {
            for (Iterator it = temp1[j].begin(); it < temp1[j].end(); it++)
            {
                szj = szamjegy (*it, i);
                temp2[szj].push_back(*it);
            }
        }
        temp1 = temp2;
        i++;
    }

    x = temp1[0];
}

void write_vector (const Vektor& temp)
{
    for (cIterator it = temp.begin(); it < temp.end(); it+=10)
        g << *it << " ";
}

int n, i, temp, a, b, c;
Vektor x;

int main()
{
    f >> n >> a >> b >> c;
    x.push_back(b);

    for (i=1; i<n; i++)
    {
        temp = (a*x[i-1]+b)%c;
        x.push_back(temp);
    }

    radix_sort (x);
    write_vector(x);
}