Cod sursa(job #662612)

Utilizator andumMorie Daniel Alexandru andum Data 16 ianuarie 2012 20:46:04
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <cstdio>
#include <queue>

using namespace std;

int a[500005],n,maxim,i;
queue <int> galeti[256];

void radix()
{
	int i=0,j,x,k;
	while (maxim)
	{
		for (j=1;j<=n;++j)
		{
			x=(a[j]>>i)&255;
			galeti[x].push(a[j]);
		}
		k=0;
		for (j=0;j<256;++j)
		{
			while (!galeti[j].empty())
			{
				a[++k]=galeti[j].front();
				galeti[j].pop();
			}
		}
		maxim>>=8;
		i+=8;
	}
}

int main()
{
	freopen("algsort.in", "r", stdin);
	freopen("algsort.out", "w", stdout);

	scanf("%d", &n);
	maxim=0;
	for (i=1;i<=n;++i)
	{
		scanf("%d", &a[i]);
		if(a[i]>maxim)
            maxim=a[i];
	}
	radix();
	for (i=1;i<=n;++i)
		printf("%d ", a[i]);

	return 0;
}