Cod sursa(job #649961)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 16 decembrie 2011 23:15:11
Problema Sortare prin comparare Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
#include <queue>

#define NMax 500001
#define Bits 8

using namespace std;

queue <long> Buckets[1<<Bits];
long V[NMax], N, Max, S=1<<Bits;

void RadixSort()
{
	for (long i=0; Max; Max>>=Bits, i+=Bits)
	{
		for (long j=1; j<=N; ++j)
		{
			int Place=((V[j]>>i)&255);
			Buckets[Place].push(V[j]);
		}
		long aux=0;
		for (long j=0;j<=255;++j
		{
			while (!Buckets[j].empty()
            {
				V[++aux]=Buckets[j].front();
				Buckets[j].pop();
			}
		}
	}
}

void Read ()
{
    freopen ("algsort.in", "r", stdin);
    scanf ("%ld", &N);
    for (long i=1; i<=N; ++i)
    {
        scanf ("%ld", &V[i]);
        if (V[i]>Max)
        {
            Max=V[i];
        }
    }
}

void Print ()
{
    freopen ("algsort.out", "w", stdout);
    for (long i=1; i<=N; ++i)
    {
        printf ("%ld ", V[i]);
    }
}

int main ()
{
	Read ();
    RadixSort ();
	Print ();
	return 0;
}