Pagini recente » Cod sursa (job #768064) | Diferente pentru runda/redsnow_2 intre reviziile 21 si 44 | Statistici Razvan Gogu (gogurazvan) | Cod sursa (job #2685328) | Cod sursa (job #443391)
Cod sursa(job #443391)
#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;
}