Cod sursa(job #2223404)

Utilizator paul_danutDandelion paul_danut Data 20 iulie 2018 08:25:06
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("radixsort.in");
ofstream g("radixsort.out");



const int MAXN = 10000000;
const int COUNTSIZE = 256;
const int BUCKETSIZE = 8;

int N, A, B, C;

int v[MAXN+1];
int temp_v[MAXN+1];
int index[COUNTSIZE+1];
int frequence[COUNTSIZE+1];

int mask = (1 << BUCKETSIZE) - 1;


int compute_index(int val, int bucket)
{
	int c = val >> (bucket * BUCKETSIZE) & mask;
	return c;
}

void initialize()
{
	for (int i = 0; i <= COUNTSIZE; i++)
	{
		index[i] = 0;
		frequence[i] = 0;
	}
}

void sort()
{
	initialize();
	int i, j, pos;
	for (i = 0; i<4; i++)
	{
		initialize();
		int c;
		for (j = 1; j <= N; j++)
		{
			c = compute_index(v[j], i);
			frequence[c]++;
		}

		index[0] = 0;
		int count = frequence[0];
		for (j = 1; j <= COUNTSIZE; j++)
		{
			if (frequence[j])
			{
				index[j] = count;
				count += frequence[j];
			}
		}

		for (j = 1; j <= MAXN; j++)
		{
			pos = compute_index(v[j], i);
			temp_v[index[pos] + frequence[pos]] = v[j];
			frequence[pos] --;
		}

		for (j = 1; j <= MAXN; j++)
		{
			v[j] = temp_v[j];
		}
	}
}

int main()
{
	f >> N >> A >> B >> C;

	v[1] = B;
	for (int i = 2; i <= MAXN; i++)
	{
		v[i] = (A * v[i - 1] + B) % C;
	}

	sort();

	for (int j = 1; j <= MAXN; j++)
	{
		g << v[j] << ' ';
	}

	return 0;
}