Cod sursa(job #2741211)

Utilizator muiepulicimatacutactu muiepulici Data 15 aprilie 2021 18:20:21
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>

unsigned long v[10000001];

void CountSort(unsigned long* v, int n, unsigned long exp, unsigned long* temp) {
	int i;
	int min = 9;
	int max = 0;

	int digit;

	int count[10] = { 0 };

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

		++count[digit];

		if (digit < min)
			min = digit;

		if (digit > max)
			max = digit;
	}

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

	int poz;

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

		--count[digit];
	}

	for (i = 0; i < n; ++i)
		v[i] = temp[i];
}

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

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

	unsigned long* temp = new unsigned long[n];

	for (unsigned long exp = 1; max / exp > 0; exp *= 10)
		CountSort(v, n, exp, temp);

	delete[] temp;
}

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

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

	v[0] = B;

	int i;

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

	RadixSort(v, N);

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

	fin.close();
	fout.close();

	return 0;
}