Cod sursa(job #2649496)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 14 septembrie 2020 22:51:13
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <cstdio>

using namespace std;

void radixsort(int numbers[], int n) {

}


int main () {
	freopen("radixsort.in", "r", stdin);
	freopen("radixsort.out", "w", stdout);

	int n, a, b, c;
	scanf("%d", &n);
	int numbers[n+1];
    scanf("%d%d%d", &a, &b, &c);
    numbers[0] = b;
    for(int i=1; i<n; ++i)
        numbers[i] = (a * numbers[i-1] + b) % c;

    int buckets[10][n];

	bool has_digit = true;
	int current_digit = 1, current;

	while(has_digit) {
		has_digit = false;

		for(int i=0; i<=9; ++i)
			buckets[i][0] = 0;

		for(int i=0; i<n; ++i) {
			current = numbers[i] / current_digit % 10;
			buckets[current][++ buckets[current][0]] = numbers[i];
			if (numbers[i] / (current_digit*10) != 0)
				has_digit = true;
		}

		current = 0;
		for(int i=0; i<=9; ++i)
			for(int j=1; j<=buckets[i][0]; ++j)
				numbers[current++] = buckets[i][j];

		current_digit *= 10;

	}

	for(int i=0; i<n; i+= 10)
		printf("%d ", numbers[i]);

	return 0;
}