Pagini recente » Profil Pepelea_Flaviu | Cod sursa (job #277766) | Cod sursa (job #2756875) | Cod sursa (job #403604) | Cod sursa (job #2230852)
#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;
}