Cod sursa(job #659089)

Utilizator DraStiKDragos Oprica DraStiK Data 9 ianuarie 2012 23:52:41
Problema Sortare prin comparare Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

#define MOD (1<<8)-1
#define CANS 8


ifstream fin ("algsort.in");
ofstream fout ("algsort.out");

queue <int> bucket[MOD+5];
vector <int> v;
int N,max_val;

void read ()
{
	fin>>N;
	v.resize (N+5);
	for (int i=1; i<=N; ++i)
	{
		fin>>v[i];
		max_val=max (max_val,v[i]);
	}
}

void radix ()
{
	for (int bit=0; max_val; bit+=CANS, max_val>>=CANS)
	{
		for (int i=1; i<=N; ++i)
			bucket[(v[i]>>bit)&MOD].push (v[i]);

		int newN=0;
		for (int i=0; i<MOD; ++i)
			while (!bucket[i].empty ())
				v[++newN]=bucket[i].front (), bucket[i].pop ();
	}

}

void print ()
{
	for (int i=1; i<=N; ++i)
		fout<<v[i]<<" ";
}

int main ()
{
	read ();
	radix ();
	print ();

	return 0;
}