Cod sursa(job #1759963)

Utilizator andreioneaAndrei Onea andreionea Data 20 septembrie 2016 01:50:24
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <array>

struct file_manip {

	std::ifstream fin;
	std::ofstream fout;

	file_manip(const char* filename) {
		std::string infilename  = std::string(filename) + ".in";
		std::string outfilename = std::string(filename) + ".out";
		fin.open(infilename.c_str());
		fout.open(outfilename.c_str());
	}

	template <class T>
	file_manip& operator << (const T& rhs) {
		fout << rhs;
		return *this;
	}
	template <class T>
	file_manip& operator >> (T& rhs) {
		fin >> rhs;
		return *this;
	}
};


int main()
{
	std::vector<int> u, v;
	std::array<int, 256> bucket_items;
	std::array<int, 256> bucket_running_index;
	int n,a,b,c;
	file_manip fm("radixsort");
	
	fm >> n >> a >> b >> c;

	v.resize(n);
	u.resize(n);

	v[0] = b;

	for (auto i = 1; i < n; ++i)
		v[i] = ((v[i - 1] * a  + b) % c);

	for (int byte_count = 0; byte_count < 4; ++byte_count)
	{
		std::fill_n(bucket_items.begin(), 256, 0);
		std::fill_n(bucket_running_index.begin(), 256, 0);
		for (const auto i : v) {
			const auto bucket = (i >> (8 * byte_count)) & 0xff;
			++bucket_items[bucket];
		}

		for (int idx = 1; idx < 256; ++idx){
			bucket_running_index[idx] = bucket_running_index[idx - 1] + bucket_items[idx - 1];
		}

		for (const auto i : v) {
			const auto bucket = (i >> (8 * byte_count)) & 0xff;
			u[bucket_running_index[bucket]++] = i;
		}

		v.swap(u);
	}

	for (auto i = 0; i < v.size(); i += 10)
		fm << v[i] << " ";

	return 0;
}