Cod sursa(job #2190351)

Utilizator AlexnolifeAlexandru Ica Alexnolife Data 30 martie 2018 16:52:39
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <fstream>
#include <array>
#include <queue>

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

int N, A, B, C;
int digits, max;
constexpr int base = 10;

std::array<int, 10000005> nums;

int GetNumOfDigits(int n)
{
	int cnt = 0;

	while (n) {
		n /= 10;
		++cnt;
	}

	return cnt;
}

void Generate()
{
	nums[0] = B;
	max = nums[0];

	for (int i = 1; i < N; ++i) {
		nums[i] = (A * nums[i - 1] + B) % C;
		
		if (nums[i] > max) {
			max = nums[i];
		}
	}

	digits = GetNumOfDigits(max);
}

//void CountSort(int digit)
//{
//	auto factor = [](int i) { 
//								int res = 1; 
//								for (int j = 1; j <= i; ++j) 
//									res *= 10; 
//
//								return res;
//							};
//
//	int i;
//	int count[11] = { 0 };
//	const int exp = factor(digit);
//
//	for (i = 0; i < N; ++i) {
//		++count[(nums[i] / exp) % base];
//	}
//
//	for (i = 1; i < base; ++i) {
//		count[i] += count[i - 1];
//	}
//
//	for (i = N - 1; i >= 0; --i) {
//		nums[count[(nums[i] / exp) % base] - 1] = nums[i];
//		
//	}
//}

void Sort()
{
	int i, j, factor;
	
	std::queue<int> q[base];
	
	for (i = 0, factor = 1; i < digits; ++i, factor *= base) {
		for (j = 0; j < N; ++j) {
			q[(nums[j] / factor) % base].emplace(nums[j]);
		}
		
		int k = 0;
	
		for (int l = 0; l < base; ++l) 
			while (!q[l].empty()) {
				nums[k] = q[l].front();
				q[l].pop();
				++k;
			}
	}

	//for (int i = 1; i <= digits; ++i) {
	//	CountSort(i);
	//}
}

void Print()
{
	for (int i = 0; i < N; i = i + 10) {
		g << nums[i] << ' ';
	}
}

int main(int, char *[])
{
	f >> N >> A >> B >> C;
	
	Generate();
	Sort();
	Print();

	return 0;
}