Cod sursa(job #978872)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 29 iulie 2013 22:20:24
Problema Sortare prin comparare Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

const int digits = 2;        //Digits
const int r = 10;            //Bits
const int radix = 1 << r;    //Buckets
const int mask = radix - 1;  //BitMask

void RadixSort( vector<int>& a )
{
    const int SIZE = a.size();

    vector <int> b( SIZE );
    vector <int> bucket( radix );

    for ( int i = 0, shift = 0; i < digits; ++i, shift += r )
    {
        for ( int j = 0; j < radix; ++j )
                bucket[j] = 0;

        for ( int j = 0; j < SIZE; ++j )
                ++bucket[ ( a[j] >> shift ) & mask ];

        for ( int j = 1; j < radix; j++ )
                bucket[j] += bucket[j - 1];

        for ( int j = SIZE - 1; j >= 0; --j )
                b[ --bucket[ ( a[j] >> shift ) & mask ] ] = a[j];

        for ( int j = 0; j < SIZE; j++ )
                a[j] = b[j];
    }
}

void read( vector<int>& a )
{
    ifstream f("algsort.in");

    int n;
    f >> n;

    string FileData( ( istreambuf_iterator<char> ( f ) ) , istreambuf_iterator < char > ( ) ) ;

    int l = FileData.length();
    int nr = 0;

    for ( int i = 1; i < l; ++i )
            if ( isdigit( FileData[i] ) )
                    nr = nr * 10 + ( FileData[i] - 48 );
            else
            {
                a.push_back( nr );
                nr = 0;
            }

    f.close();
}

void write( vector<int> a )
{
    ofstream g("algsort.out");

    for ( int i = 0; i < a.size(); i++ )
            g << a[i] << " ";

    g << "\n";

    g.close();
}

int main()
{
    vector<int> v;

    read(v);
    RadixSort(v);
    write(v);

    return 0;
}