Cod sursa(job #2644139)

Utilizator madalin_frFrincu Madalin madalin_fr Data 23 august 2020 16:12:24
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define NMAX 10000002
using namespace std;

int getMax(int Array[], int n) {
	int mx = Array[0];
	for (int i = 1; i < n; i++)
		if (Array[i] > mx)
			mx = Array[i];
	return mx;
}

void countsort(int Array[], int n, int exp) {
	int* output = new int[n];
	int i, count[10] = { 0 };
	for (i = 0; i < n; i++) {
		count[Array[i] / exp % 10]++;
	}
	for (i = 1; i < 10; i++) {
		count[i] += count[i - 1];
	}
	for (i = n - 1; i >= 0; i--) {
		output[count[Array[i] / exp % 10] - 1] = Array[i];
		count[Array[i] / exp % 10]--;
	}
	for (i = 0; i < n; i++) {
		Array[i] = output[i];
	}
	delete output;
}

void radixsort(int Array[], int n) {
	int m = getMax(Array, n);
	for (int exp = 1; m / exp > 0; exp *= 10)
		countsort(Array, n, exp);
}

int main()
{
	int* myArray = new int[NMAX];
	long long n, a, b, c;
	ifstream fin("radixsort.in");
	ofstream fout("radixsort.out");
	fin >> n >> a >> b >> c;
	myArray[0] = b % c;
	for (int i = 1; i < n; i++) {
		myArray[i] = ((1LL * a * myArray[i - 1]) + b) % c;
 	}
	radixsort(myArray, n);
	for (int i = 0; i < n; i+=10) {
		fout << myArray[i] << " ";
	}
	fout.close();
}