Cod sursa(job #2230852)

Utilizator TrixerAdrian Dinu Trixer Data 11 august 2018 22:18:02
Problema Radix Sort Scor 30
Compilator c Status done
Runda Arhiva educationala Marime 1.26 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NMAX 		10000001
#define RADIX 		0xFF
#define RADIX_SIZE	8
#define NBYTES		sizeof(int)

#define get_byte(x, b) (((x) >> (RADIX_SIZE * (b))) & RADIX)

int n, a, b, c;
int *v, *w, *aux;
int count[1 << RADIX_SIZE];
int idx[1 << RADIX_SIZE];

void countsort(int byte)
{
	memset(count, 0, sizeof(count));

	// count occurences of the byte'th byte
	for (int i = 0; i < n; i++)
	       count[get_byte(v[i], byte)]++;

	// calculate the starting index of each key
	idx[0] = 0;
	for (int i = 1; i < (1 << RADIX_SIZE); i++)
		idx[i] = idx[i - 1] + count[i - 1];

	// sort by byte
	for (int i = 0; i < n; i++)
		w[idx[get_byte(v[i], byte)]++] = v[i];

	aux = v;
	v = w;
	w = aux;
}

void radixsort()
{
	// sort by each 8bit digit (LSD first)
	for (int i = 0; i < NBYTES; i++)
		countsort(i);
}

int main()
{
	// read input
	freopen("radixsort.in", "r", stdin);
	scanf("%d%d%d%d", &n, &a, &b, &c);

	// generate numbers
	v = malloc(n * sizeof(int));
	w = malloc(n * sizeof(int));
	v[0] = b % c;
	for (int i = 1; i < n; i++)
		v[i] = (a * v[i - 1] % c + b) % c;

	// sort
	radixsort();

	// print output
	freopen("radixsort.out", "w", stdout);
	for (int i = 0; i < n; i += 10)
		printf("%d ", v[i]);

	free(v);
	free(w);

	return 0;
}