Cod sursa(job #1095158)

Utilizator marius135Dumitran Adrian Marius marius135 Data 30 ianuarie 2014 15:12:52
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<stdio.h>
#include<string.h>
#include<iostream>

using namespace std;
#define maxn 10000001

int N;
int aux[maxn];
int v[maxn];

void radix( int *v) {
	
	int mod = (1<<8);
	int last_mod = 0;
	int count[256], sum[256];
	memset(count, 0, sizeof(count));
	
	for( int i = 1; i <= 4; ++i) {
		
		for( int j = 0; j < N; ++j) 
			count[ (v[j]&(mod-1)) >>last_mod]++; 
		sum[0] = 0;
		for( int i = 1; i < 256; ++i)
			sum[i] = sum[i-1] + count[i-1];
		for( int j = 0; j < N; ++j)
			aux[ sum[ (v[j]&(mod-1)) >> last_mod]++] = v[j];
		for( int j = 0; j < N; ++j)
			v[j] = aux[j];
		
		
		last_mod += 8;
		mod = (mod<<8);
	}
	
}

int main() {

	freopen("radix.in", "r", stdin);
	freopen("radix.out", "w" ,stdout);
	
	int a = 12, b = 38, c = 123;
	N = 100;

	scanf("%d %d %d %d", &N, &a, &b, &c);
	
	v[0] = b;
	for( int i = 1; i < N; ++i)
		v[i] = ((long long)a * v[i-1] + b) % c;
	
	radix(v);
	//sort(v, v+N);
	
	for( int i = 0; i < N; i+= 10)
		cout<<v[i]<<" ";
	
	return 0;
}