Cod sursa(job #1472354)

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

#define NMAX 10000005

int v[NMAX], n;
int bucket[10][NMAX], count[10];

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 radixsort () {
	unsigned long b = 1;
	
	for (int i = 1; i <= 10; ++i) {
		for (int j = 0; j < n; ++j) {
			int pos = (v[j] / b) % 10;
			bucket[pos][count[pos]] = v[j];
			++count[pos];
		}
		
		int *p = v;
		for (int j = 0; j < 10; ++j) {
			memmove(p, bucket[j], count[j] * sizeof(int));
			p += count[j];
			count[j] = 0;
		}
		
		b *= 10;
	}
}
 

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;
}