Cod sursa(job #2702660)

Utilizator DragosC1Dragos DragosC1 Data 5 februarie 2021 12:22:22
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <vector>
using namespace std;

vector<int> a(10000000 + 1);
int n;

int maxelement() {
	int i, maxim;
	for (i = 1; i <= n; i++)
		if (a[i] > maxim)
			maxim = a[i];
	return maxim;
}

int digits(int x) {
	int nr = 0;
	do {
		nr++;
		x /= 10;
	} while (x > 0);
	return nr;
}

void RadixSort() {
	int i, x, j, nr;
	int Max = maxelement();
	int maxdig = digits(Max);
	long long p = 1;
	while (maxdig > 0) {
		nr = 0;
		vector<int> bucket[10];
		maxdig--;
		for (i = 1; i <= n; i++) {
			x = (a[i] / p) % 10;
			bucket[x].push_back(a[i]); 
		}
		for (i = 0; i <= 9; i++)
			for (j = 0; j < bucket[i].size(); j++) {
				nr++;
				a[nr] = bucket[i][j];
			}
		p *= 10;
	}
}

int main() {
	ios::sync_with_stdio(0);
	int x, y, z, i;

	ifstream f("radixsort.in");
	f >> n >> x >> y >> z;
	a[1] = y;
	for (i = 2; i <= n; i++)
		a[i] = (x * a[i - 1] + y) % z;
	f.close();

	RadixSort();

	ofstream g("radixsort.out");
	for (i = 1; i <= n; i += 10)
		g << a[i] << ' ';
	g.close();

	return 0;
}