Cod sursa(job #1472425)

Utilizator aimrdlAndrei mrdl aimrdl Data 17 august 2015 04:49:41
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <stdio.h>
#include <string.h>

#define NMAX 10000005
#define MASK 255

int v[NMAX], temp[NMAX], n;

void vgen () {
	int a, b, c;
	
	scanf("%d %d %d %d", &n, &a, &b, &c);
	
	v[0] = b;
	for (int i = 1; i < n; ++i) {
		v[i]  = (a * v[i-1] + b) % c;
	}
}
/*
void alloc() {
	for (int i = 0; i < 10; ++i) {
		bucket[i] = malloc(NMAX * sizeof(int));
	}
} 
*/

void countsort(int *v, int *u, int x) {
	int f[256] = {0};
	
	int p = 8 * x;
	
	for (int i = 0; i < n; ++i) {
		++f[(v[i] >> p) & MASK];
	}
	
	for (int i = 1; i < 256; ++i) {
		f[i] += f[i-1];
	}
	 
	for (int i = n-1; i >= 0; --i) {
		int pos = v[i] >> p & MASK;
		--f[pos]; 
		u[f[pos]] = v[i];
	}
}

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

int main (void) {
	freopen("radixsort.in", "r", stdin);
	freopen("radixsort.out", "w", stdout);
	
	vgen();
//	alloc();
	radixsort();
	
	for (int i = 0; i < n; i+=10) {
		printf("%d ", v[i]);
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}