Cod sursa(job #1223058)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 25 august 2014 13:03:52
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<cstdio>
#include<vector>
#define	NMAX 10000010
#define BYTE 8
using namespace std;

unsigned int V[NMAX];
int N; 

void read() {

	freopen("radixsort.in", "r", stdin);
	freopen("radixsort.out", "w", stdout);

	unsigned int A, B, C;
    scanf("%d %u %u %u", &N, &A, &B, &C);
    
	V[1] = B;
	for (int i = 2 ; i <= N ; i++)
		V[i] = (A * V[i - 1] + B) % C;
}

unsigned int get_byte(unsigned int val, int byte) {
	return (val >> (byte * BYTE)) & ((1<<BYTE) - 1);
}

void count_sort(int c_byte) {

    vector<unsigned int> Count[1<<BYTE];
	for (int i = 0 ; i < 1<<BYTE ; i++)
		Count[i].clear();

	for (int i = 1 ; i <= N ; i++)
		Count[get_byte(V[i], c_byte)].push_back(V[i]);

	for (int i = 0, k = 0 ; i < 1<<BYTE; i++)
		for (vector<unsigned int> :: iterator it = Count[i].begin() ; it != Count[i].end() ; it++)
			V[++k] = *it; 
}

void radix_sort() {

	for (int c_byte = 0 ; c_byte <= 3 ; c_byte++)
		count_sort(c_byte);
}

void print() {

	for (int i = 1 ; i <= N ; i += 10)
		printf("%u ", V[i]);
	printf("\n");
}


int main() { 

	read();
    radix_sort();
	print();

	return 0;
}