Cod sursa(job #567633)

Utilizator rootsroots1 roots Data 30 martie 2011 11:54:26
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <stdio.h>
#include <string.h>

#define Dim 500001

int v[Dim],w[Dim];
int N;

void radix(int pas,int v[],int w[])
{
	int cnt[256],ind[256];
	int i;

	memset(cnt,0,sizeof(cnt));

	for(i=1;i<=N;i++) cnt[((v[i]>>(8*pas))&((1<<8)-1))]++;
	ind[0]=1;
	for(i=1;i<256;i++) ind[i]=ind[i-1]+cnt[i-1];
	for(i=1;i<=N;i++) w[ind[((v[i]>>(8*pas))&((1<<8)-1))]++]=v[i];
}

int main()
{
	int i;

	freopen("algsort.in","r",stdin);

	scanf("%d",&N);
	for(i=1;i<=N;i++) scanf("%d",&v[i]);

	radix(0,v,w);
	radix(1,w,v);
	radix(2,v,w);
	radix(3,w,v);

	freopen("algsort.out","w",stdout);

	for(i=1;i<N;i++) printf("%d ",v[i]);
	printf("%d\n",v[N]);

	return 0;
}