Cod sursa(job #2291213)

Utilizator VadimCCurca Vadim VadimC Data 27 noiembrie 2018 19:16:53
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

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

#define NMax 10000010
#define d 10

int n, A, B, C;
int a[NMax], b[NMax], index[d + 5];

void citire();
void radix_sort();
void counting_sort(int);
unsigned int cifra(int, int);
void afisare();

int main(){
	citire();
	radix_sort();
	afisare();
}

void citire(){
	fin >> n >> A >> B >> C;
	a[0] = B;
	for(int i = 1; i < n; i++)
		a[i] = (A * a[i - 1] + B) % C;
}

void radix_sort(){
	int i;
	for(i = 1; i <= d; i++)
		counting_sort(i);
}

void counting_sort(int nr){
	int i;
	fill(index, index + d + 5, 0);
	for(i = 0; i < n; i++) index[cifra(a[i], nr)]++;
	for(i = 1; i <= d; i++) index[i] += index[i - 1];
	for(i = n - 1; i >= 0; i--){
		b[index[cifra(a[i], nr)] - 1] = a[i];
		index[cifra(a[i], nr)]--;
	}
	for(i = 0; i < n; i++) a[i] = b[i];
}

unsigned int cifra(int x, int nr){
	x /= pow(10, nr - 1);
	return x % 10;
}

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