Cod sursa(job #2222789)

Utilizator AlexDabuDabu Alexandru AlexDabu Data 18 iulie 2018 01:07:34
Problema Radix Sort Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>

#define NMAX 10000002
#define RADIX 0xFF
#define RADIX_SIZE 8
#define TOTAL_BYTES sizeof(numberList[0])
#define get_byte(x) ((x>>(byte * 8))&RADIX)

using namespace std;

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

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

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

void Countsort(int A[], int B[], int byte)
{
	int counter[1 << RADIX_SIZE] = { 0 };
	int index[1 << RADIX_SIZE] = { 0 };

	for (int i = 0; i < n; i++)
		++counter[get_byte(A[i])];

	for (int i = 1; i < 1 << RADIX_SIZE; i++)
		index[i] = index[i - 1] + counter[i - 1];

	for (int i = 0; i < n; i++)
		B[index[get_byte(A[i])]++] = A[i];
}

void RadixSort(void)
{
	for (int i = 0; i < TOTAL_BYTES; i++)
	{
		if (i % 2 == 0)
			Countsort(numberList, semiSorted, i);
		else
			Countsort(semiSorted, numberList, i);
	}
}

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

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