Cod sursa(job #2222771)

Utilizator AlexDabuDabu Alexandru AlexDabu Data 18 iulie 2018 00:35:42
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>

#include <fstream>
#include <vector>

#define NMAX 10000002

using namespace std;

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

int n, a, b, c;
int numberList[NMAX] , semiSorted[NMAX];
int max = 0;

void Read(void)
{
	fin >> n >> a >> b >> c;
	numberList[1] = b;
	for (int i = 2; i <= n; i++)
	{
		numberList[i] = (a * numberList[i - 1] + b) % c;
	}
}

void GetMax(int& maxim)
{
	for (int i = 1; i <= n; i++)
	{
		if (maxim < numberList[i]) maxim = numberList[i];
	}
}

void RadixSort(void)
{
	int significantDigit = 1;
	while (max / significantDigit > 0)
	{
		int bucket[10] = { 0 };
		for (int i = 1; i <= n; i++)
		{
			bucket[(numberList[i] / significantDigit) % 10]++;
		}

		for (int i = 1; i < 10; i++)
		{
			bucket[i] += bucket[i - 1];
		}

		for (int i = n; i > 0; i--)
		{
			semiSorted[--bucket[(numberList[i] / significantDigit) % 10]] = numberList[i];
		}

		for (int i = 1; i <= n; i++)
		{
			numberList[i] = semiSorted[i];
		}

		significantDigit *= 10;
	}
}

void Print(void)
{
	for (int i = 1; i <= n; i += 10)
	{
		fout << numberList[i] << ' ';
	}
}

int main(void)
{
	Read();
	GetMax(max);
	RadixSort();
	Print();
	return 0;
}