Cod sursa(job #443391)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 16 aprilie 2010 21:18:33
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <algorithm>
#include <fstream>

using namespace std;

const char Input[] = "algsort.in";
const char Output[] = "algsort.out";

const int Dim = 500001;

int N, A[Dim], R[Dim];

void radix( int left, int right, int bit ) {

    int i, j, x, y, mid, base;

    if( !bit || left == right )
        return;

    x = 0;
    y = right - left + 2;
    base = 1 << (bit - 1);

    for( i = left; i <= right; ++i ) {

        if( A[i] & base )
            R[--y] = A[i];
        else
            R[++x] = A[i];
    }

    if( x == 0 || y == right - left + 2 ) {

        radix( left, right, bit - 1 );
        return;
    }

    for( i = 1, j = left; i <= N && j <= right; ++i, ++j )
        A[j] = R[i];

    mid = left + x - 1;

    radix( left, mid, bit - 1 );
    radix( mid + 1, right, bit - 1 );
}


int main() {

    ifstream fin( Input );
    ofstream fout( Output );

    int i;

    fin >> N;
    for( i = 1; i <= N; ++i )
        fin >> A[i];

    radix( 1, N, 31 );

    for( i = 1; i <= N; ++i )
        fout << A[i] << " ";

    fin.close();
    fout.close();

    return 0;
}