Cod sursa(job #1473216)

Utilizator glbglGeorgiana bgl glbgl Data 18 august 2015 20:33:05
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;


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

int N, A, B, C;

void CountingSort(int input[], int exp){

	int output[N+1], count[10] = {0};

	for(int i = 1; i <= N; ++i)
		++count[(input[i]/exp)%10];

	for(int i = 1; i < 10; ++i)
		count[i] += count[i-1];

	for(int i = N; i > 0; --i){
		output[count[(input[i]/exp)%10] - 1] = input[i];
		--count[(input[i]/exp)%10];
	}

	for(int i = 1; i <= N; ++i){
		input[i] = output[i-1];
	}	
}


void RadixSort(int input[]){

	int max = *max_element(input+1, input+N);

	for(int exp = 1; max/exp > 0; exp *= 10)
		CountingSort(input, exp);

	for(int i = 1; i <= N; i += 10)
		out << input[i] << ' ';
}


int main(){

	in >> N >> A >> B >> C;
	
	int input[N+1];
	
	input[0] = 0;
	input[1] = B;
	
	for(int i = 2; i <= N; ++i)
		input[i] = (1LL * A * input[i-1] + B) % C;

	RadixSort(input);
	
	return 0;
}