Cod sursa(job #1111865)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 19 februarie 2014 10:38:22
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <vector>

inline void countsort(const std::vector<unsigned> &from, std::vector<unsigned> &to, unsigned byte){
	unsigned k[256],kc[256];
	kc[0]=0;
	for(unsigned i=0;i<256;++i){ k[i]=0; }
	for(unsigned i=0;i<from.size();++i) k[(from[i]>>(8*byte))&0xFF]++;
	for(unsigned i=1;i<256;++i) kc[i]=kc[i-1]+k[i-1];

	for(unsigned i=0;i<from.size();++i) to[kc[(from[i]>>(8*byte))&0xFF]++]=from[i];
}


int main(){
	std::ifstream fin("radixsort.in");
	std::ofstream fout("radixsort.out");

	unsigned N,A,B,C;
	fin>>N>>A>>B>>C;

	std::vector<unsigned> a(N),b(N);

	a[0]=B;
	for(unsigned i=1;i<N;++i){
		a[i]=(A*a[i-1]+B)%C;
	}

	countsort(a,b,0);
	countsort(b,a,1);
	countsort(a,b,2);
	countsort(b,a,3);

	for(unsigned i=0;i<N;i+=10)	fout<<a[i]<<' ';

	fout<<'\n';
}