Cod sursa(job #2562626)

Utilizator MicuMicuda Andrei Micu Data 29 februarie 2020 16:22:56
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream in("radixsort.in");
ofstream out("radixsort.out");

void RadixSortBase256(vector<int>& v) {
	//aflam numarul minimul din vector
	int n = v.size(), mn = v[0];
	for (int i = 0; i < n; i++) {
		if (v[i] < mn) mn = v[i];
	}
	
	//daca vectorul contine elemente negative, scadem minimul pentru a sorta un vector doar de elemente pozitive
	if (mn < 0) {
		for (int i = 0; i < n; i++) v[i] -= mn;
	}
	
	vector<int> liste[256];
	
	for (int i = 0; i < n; i++) {
		liste[(v[i] & 255)].push_back(v[i]);
	}
	
	//mutam valorile din liste inapoi in vector
	v.clear();
	for (int i = 0; i < 256; i++) {
		for (int j = 0; j < liste[i].size(); j++) v.push_back(liste[i][j]);
		liste[i].clear();
	}
	
	int bits = 8;
	bool ok = false;
	while (!ok) {
		for (int i = 0; i < n; i++) {
			liste[((v[i] >> bits) & 255)].push_back(v[i]);
		}
	
		//mutam valorile din liste inapoi in vector
		v.clear();
		//daca am procesat cifrele tuturor numerelor, inseamna ca vectorul este sortat
		if (liste[0].size() == n) ok = 1;
		for (int i = 0; i < 256; i++) {
			for (int j = 0; j < liste[i].size(); j++) v.push_back(liste[i][j]);
			liste[i].clear();
		}
	
		bits += 8;
	}
	
	//daca vectorul continea initial valori negative, adaugam minimul acestora pentru a obtine valorile initiale din vector
	if (mn < 0) {
		for (int i = 0; i < n; i++) v[i] += mn;
	}
}

int main() {
	int n, a, b, c;
	vector <int> v;
	in >> n >> a >> b >> c;
	v.push_back(b);
	for (int i = 1; i < n; i++) {
		v.push_back((a * v[i - 1] + b) % c);
	}
	RadixSortBase256(v);
	for (int i = 0; i < n; i += 10) {
		out << v[i] << ' ';
	}
}