Pagini recente » Cod sursa (job #2248345) | Cod sursa (job #2920809) | Cod sursa (job #1317459) | Cod sursa (job #1260286) | Cod sursa (job #443396)
Cod sursa(job #443396)
#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 == 0 || 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 );
freopen( Output, "w", stdout );
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] << " ";
printf( "%d ", A[i] );
fin.close();
// fout.close();
return 0;
}