Cod sursa(job #867824)

Utilizator razvan.popaPopa Razvan razvan.popa Data 30 ianuarie 2013 10:39:33
Problema Sortare prin comparare Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<fstream>
#include<queue>
#define FOR(i,a,b)\
   for(int i=a; i<=b; ++i)
#define infile "algsort.in"
#define outfile "algsort.out"
#define nMax 200005
#define bits 8
#define vmax 255
using namespace std;

int v[nMax];

queue < int > buckets[1<<bits];

int N;

void read(){
    ifstream f(infile);

    f >> N;

    FOR(i,1,N)
       f >> v[i];

    f.close();
}

void radix(){
    for(int shift = 0; shift < 31; shift += bits){
        FOR(i,1,N){
            int value = (v[i]>>shift) & vmax;
            buckets[value].push(v[i]);
        }

        v[0] = 0;
        FOR(i,0,vmax)
           while(!buckets[i].empty()){
               v[++v[0]] = buckets[i].front();
               buckets[i].pop();
           }
    }
}


void print(){
    ofstream g(outfile);

    FOR(i,1,N)
       g << v[i] << " ";

    g.close();
}

int main(){
    read();
    radix();
    print();

    return 0;
}