Pagini recente » Cod sursa (job #2071434) | Cod sursa (job #688675) | Cod sursa (job #1326317) | Cod sursa (job #180430) | Cod sursa (job #2076365)
#include <fstream>
using namespace std;
#define MAXSIZE 500001
ifstream f("algsort.in");
ofstream g("algsort.out");
int v[MAXSIZE];
int maxim,n;
void countsort(int x)
{
int counti[256] = {0};
int output[MAXSIZE];
int i;
for ( i = 1; i <= n ; i++ )
{
int aux = (v[i]>>x)&255;
counti[ aux ]++;
}
for ( i = 1; i <= 255 ; i++ )
counti[i] += counti[i-1];
for ( i = n ; i > 0 ; i-- ){
int aux = (v[i]>>x)&255;
output[ counti[ aux ]-- ] = v[i];
}
for ( i = 1; i <= n ; i++ )
v[i] = output[i];
}
void radix()
{
int biti = 0;
while ( maxim )
{
countsort(biti);
biti += 8;
maxim = maxim >> 8;
}
}
void read()
{
f >> n;
for ( int i = 1; i <= n ; i++ )
{
f >> v[i];
if ( maxim < v[i] ) maxim = v[i];
}
}
void write()
{
for ( int i = 1; i <= n ; i++ )
g << v[i] << " " ;
}
int main()
{
read();
radix();
write();
return 0;
}