Cod sursa(job #978888)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 29 iulie 2013 23:30:55
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 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;
}