Mai intai trebuie sa te autentifici.
Cod sursa(job #978889)
Utilizator | Data | 29 iulie 2013 23:31:59 | |
---|---|---|---|
Problema | Sortare prin comparare | Scor | 20 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.05 kb |
#include <cstdio>
#include <queue>
#define NMax 500001
#define Bits 8
using namespace std;
queue <int> Buckets[1<<Bits];
int V[NMax], N, Max, S=1<<Bits;
void RadixSort()
{
for (int i=0; Max; Max>>=Bits, i+=Bits)
{
for (int j=1; j<=N; ++j)
{
int Place=((V[j]>>i)&127);
Buckets[Place].push(V[j]);
}
int aux=0;
for (int j=0; j<=127; ++j)
{
while (!Buckets[j].empty())
{
V[++aux]=Buckets[j].front();
Buckets[j].pop();
}
}
}
}
void Read ()
{
freopen ("algsort.in", "r", stdin);
scanf ("%ld", &N);
for (int i=1; i<=N; ++i)
{
scanf ("%ld", &V[i]);
if (V[i]>Max)
{
Max=V[i];
}
}
}
void Print ()
{
freopen ("algsort.out", "w", stdout);
for (int i=1; i<=N; ++i)
{
printf ("%ld ", V[i]);
}
}
int main ()
{
Read ();
RadixSort ();
Print ();
return 0;
}