Cod sursa(job #1472411)

Utilizator aimrdlAndrei mrdl aimrdl Data 17 august 2015 04:16:43
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <stdio.h>
#include <string.h>

#define NMAX 10000005
#define MASK 255

int v[NMAX], temp[NMAX], n;
int bucket[2][NMAX], count[2];

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 x) {
	int f[255] = {0};
	
	int p = 8 * x;
	
	for (int i = 0; i < n; ++i) {
		++f[(v[i] >> p) & MASK];
	}
	
	for (int i = 1; i < 255; ++i) {
		f[i] += f[i-1];
	}
	
	int pos = f[0];
	 
	for (int i = 1; i < 254; ++i) {
		int diff = f[i] - f[i-1];
		
		int npos = pos + diff;
		for (; pos < npos; ++pos) {
			temp[pos] = temp[pos] | (i << p);
		}	
	}
}

void radixsort () {
	for (int i = 0; i < 4; ++i) {
		countsort(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 ", temp[i]);
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}