Cod sursa(job #2649936)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 16 septembrie 2020 21:11:03
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <cstdio>

using namespace std;
void radixsort(int numbers[], int aux[], int n, int current_byte) {
	int counts[1<<8];
	for(int i=0; i< 1<<8; ++i)
		counts[i] = 0;

	int current_value;
	for(int i=0; i<n; ++i) {
		current_value = (numbers[i] >> (current_byte * 8)) & 0xFF;
		++counts[current_value];
	}

	for(int i=1; i< 1<<8; ++i)
		counts[i] += counts[i-1];

	for(int i=n - 1; i>=0; --i) {
		current_value = (numbers[i] >> (current_byte * 8)) & 0xFF;
		aux[counts[current_value]-1] = numbers[i];
		--counts[current_value];
	}
}


int numbers[10000001];
int aux[10000001];


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

	int n, a, b, c, total_bytes = sizeof(numbers[0]);

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

	for(int i=0; i<total_bytes; ++i)
		if (i%2 == 0)
			radixsort(numbers, aux, n, i);
		else
			radixsort(aux, numbers, n, i);


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


	return 0;
}