Cod sursa(job #1220453)

Utilizator ion824Ion Ureche ion824 Data 17 august 2014 13:49:01
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include<fstream>
#include<cstring>
using namespace std;
const int MASK = 0xff;
int N, numbers[10000001];
int temp[10000001];

int get_byte(int x, int byte){
	return (x >> (byte * 8)) & MASK;
}

void countsort(int A[], int B[], int byte){
	int counter[1 << 8];
	int index[1 << 8], i;
	
	memset(counter, 0, sizeof(counter));
	
	for(i = 0; i < N; ++i)
	  ++ counter[get_byte(A[i], byte)];
	
	index[0] = 0;  
	for(i = 1; i < 256; ++i) 
	  index[i] = index[i-1] + counter[i-1];
	  
	for(i=0; i < N; ++i)
	  B[ index[get_byte(A[i], byte)] ++] = A[i];
}

void radixsort(int numbers[]){
		
	for(int i = 0; i < 4; ++i)
	  if(i % 2 == 0) 
	    countsort(numbers, temp, i);
	  else
	    countsort(temp, numbers, i);
}

int main(){
	ifstream cin("radixsort.in");
	ofstream cout("radixsort.out");
	int A,B,C,i;
	
	cin >> N >> A >> B >> C;
	numbers[0] = B;
	for(i=1;i<N;++i) numbers[i] = (A * numbers[i-1] + B) % C;
	
	radixsort(numbers);
	
	for(i=0;i<N;i+=10) cout << numbers[i] << ' ';
	
	return 0;
}