Cod sursa(job #1092169)

Utilizator mihai995mihai995 mihai995 Data 26 ianuarie 2014 17:26:36
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
using namespace std;

const int N = 5e5;

int v[N], n;

ifstream in("algsort.in");
ofstream out("algsort.out");

void bitsort(int st, int dr, int M){
    if (!M || dr <= st)
        return;
    int i = st;
    for (int j = dr ; i != j ; ){
        while ( i != j && (v[i] & M) == 0 ) i++;
        while ( i != j && v[j] & M ) j--;
        if (i != j) swap(v[i], v[j]);
    }
    if (v[i] & M) i--;
    M >>= 1;
    bitsort(st, i, M);
    bitsort(i + 1, dr, M);
}

int main(){
    in >> n;
    for (int i = 0 ; i < n ; i++)
        in >> v[i];

    bitsort(0, n - 1, 1 << 30);

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

    return 0;
}