Cod sursa(job #2037938)

Utilizator robuvedVictor Robu robuved Data 12 octombrie 2017 23:11:25
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream in("radixsort.in");
ofstream out("radixsort.out");

int GetByte(int x, int p)
{
	int byte = (x >> (8 * p)) & 0xFF;
	return byte;
}
void SortByByte(vector<int>& v, vector<int>& temp, int byte)
{
	int count[256]{0};
	for (auto it = v.begin(); it != v.end(); it++)
	{
		count[GetByte(*it, byte)]++;
	}
	for (int i = 1; i < 256; i++)
	{
		count[i] += count[i - 1];
	}
	for (auto it = v.rbegin(); it != v.rend(); it++)
	{
		temp[--count[GetByte(*it, byte)]] = *it;
	}
}
void RadixSort(vector<int> & v)
{
	vector<int> temp(v.size());
	for (int i = 0; i < 4; i++)
	{
		if (i % 2)
			SortByByte(temp, v, i);
		else
			SortByByte(v, temp, i);
	}
}
int main()
{
	int N, A, B, C;
	in >> N >> A >> B >> C;
	vector<int> v(N, 0);
	v[0] = B;
	for (int i = 1; i < N; i++)
	{
		v[i] = (A * v[i - 1] + B) % C;
	}
	RadixSort(v);
	for (int i = 0; i < N; i+= 10)
	{
		out << v[i] << ' ';
	}
}