Cod sursa(job #1459938)

Utilizator adi_ispas95FMI - Adrian Ispas adi_ispas95 Data 11 iulie 2015 12:39:54
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>

using namespace std;

void CountingSort(int *a, int n, int exp){

	int *c = new int[10];
	int *b = new int[n];

	for (int i = 0; i < 10; i++)
		c[i] = 0;

	for (int i = 0; i < n; i++)
		c[(a[i] / exp) % 10]++;

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

	for (int i = n - 1; i >= 0; i--){
		b[c[(a[i] / exp) % 10] - 1] = a[i];
		c[(a[i] / exp) % 10]--;
	}

	for (int i = 0; i < n; i++)
		a[i] = b[i];

	delete[] b;
	delete[] c;
}

void RadixSort(int *a, int n, int max_n){
	
	for (int exp = 1; max_n / exp > 0; exp *= 10)
		CountingSort(a, n, exp);

}

int main(){

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

	int n, n_a, n_b, n_c, max_number = 0;
	//in >> n;
	in >> n >> n_a >> n_b >> n_c;

	int *a = new int[n];

	a[0] = n_b;

	for (int i = 1; i < n; i++){
		//in >> a[i];

		a[i] = (n_a * a[i - 1] + n_b) % n_c;

		if (max_number < a[i])
			max_number = a[i];
	}

	RadixSort(a, n, max_number);

	for (int i = 1; i < n; i += 10)
		out << a[i] << " ";

	delete[] a;
	return 0;
}