Cod sursa(job #347432)

Utilizator csizMocanu Calin csiz Data 11 septembrie 2009 23:23:28
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#include <vector>
#include <limits>
//radix
using namespace std;
int main(){
    ifstream in("algsort.in");
    ofstream out("algsort.out");
    int n;in>>n;
    vector<int> v;v.reserve(n);
    for(int i=0;i<n;i++){
        int t;in>>t;v.push_back(t);
    }
    vector<int> one;one.reserve(n);
    vector<int> zero;zero.reserve(n);
    for(int bit=1;bit!=numeric_limits<int>::min();bit=bit<<1){
        ///must move eficiently
        for(int i=0;i<n;++i){
            if(v[i]&bit) one.push_back(v[i]);
            else zero.push_back(v[i]);
        }
        v=zero;v.insert(v.end(),one.begin(),one.end());
        zero.clear();one.clear();
    }

    for(int i=0;i<n;i++){
        out<<v[i]<<" ";
    }
}