Cod sursa(job #2741592)

Utilizator muiepulicimatacutactu muiepulici Data 16 aprilie 2021 17:01:50
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>

int v[10000001];

void CountingSort(int* v, int n, int exp, int* temp) {
	int i;
	int count[10] = { 0 };

	for (i = 0; i < n; ++i)
		++count[(v[i] / exp) % 10];

	for (i = 1; i <= 9; ++i)
		count[i] += count[i - 1];

	for (i = n - 1; i >= 0; --i) {
		temp[count[(v[i] / exp) % 10] - 1] = v[i];
		--count[(v[i] / exp) % 10];
	}
}

void RadixSort(int* v, int n) {
	int i;
	int max = 0;

	for (i = 0; i < n; ++i) {
		if (v[i] > max)
			max = v[i];
	}

	int j;
	int* temp = new int[n];

	for (i = 1, j = 0; max / i > 0; i *= 10, ++j) {
		if (j % 2 == 0)
			CountingSort(v, n, i, temp);
		else
			CountingSort(temp, n, i, v);
	}

	if (j % 2 == 1)
		CountingSort(temp, n, i, v);

	delete[] temp;
}

int main() {	
	std::ifstream fin("radixsort.in");
	std::ofstream fout("radixsort.out");

	int N, A, B, C;
	fin >> N >> A >> B >> C;

	fin.close();

	v[0] = B;

	int i;

	for (i = 1; i < N; ++i)
		v[i] = (1LL * A * v[i - 1] + B) % C;

	RadixSort(v, N);

	for (i = 0; i < N; i += 10)
		fout << v[i] << ' ';
	
	fout.close();

	return 0;
}