Cod sursa(job #1428853)

Utilizator stef93Stefan Gilca stef93 Data 5 mai 2015 10:43:11
Problema Radix Sort Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <cstring>
#include <cstdio>

using namespace std;

void sorteaza(int *vec, int *aux, int byte, int n)
{
	int count[1 << 8];
	int index[1 << 8];

	memset(count, 0, sizeof(count));

	for(int i =0 ; i < n; i++)
	{
		count[(vec[i] >> (8*byte)) & 0xff]++;
	}

	index[0] = 0;

	for(int i = 1 ; i < (1 << 8); i++)
	{
		index[i] = index[i - 1] + count[i - 1];
	}

	for(int i = 0 ;i < n ; i++)
	{
		aux[index[(vec[i] >> (8*byte)) & 0xff] ++] = vec[i];
	}
}

int vec[10000001];
int main()
{
	ifstream in("radixsort.in");
	//ofstream out("radixsort.out");
	FILE * out = freopen("radixsort.out", "w", stdout);
	int n, a, b, c;
	int  *aux;

	in >> n >> a >> b >> c;

	//vec = new int[n];
	aux = new int[n];

	vec[0] = b;

	for(int i = 1 ; i < n; i++)
	{
		vec[i] = ((long long)a * vec[i - 1] + b) %c;
	}

	for(int i = 0 ; i <8; i++)
	{
		if(i % 2 == 0)
		{
			sorteaza(vec, aux, i, n);
		}
		else
		{
			sorteaza(aux, vec, i, n);
		}
	}

	for(int i = 0 ; i < n; i += 10)
	{
		printf("%d ", vec[i]);
	}
	return 0;
}