Pagini recente » Cod sursa (job #2268505) | Atasamentele paginii Profil Vladimir_Albu | Cod sursa (job #1477640) | Cod sursa (job #1016808) | Cod sursa (job #3357654)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define NR_CNT_SORTS 4
#define RADIX_BYTES 1
#define RADIX_BITS (RADIX_BYTES << 3)
#define RADIX_MASK (1 << RADIX_BITS) - 1
int get_val_block(int x, int nr_block)
{
return (x >> (nr_block * RADIX_BITS)) & RADIX_MASK;
}
void count_sort(int *v, int *next_v, int n, int nr_block)
{
int *cnt = (int *) calloc(RADIX_MASK + 1, sizeof(int));
int *psum = (int *) calloc(RADIX_MASK + 1, sizeof(int));
for (int i = 0; i < n; i++) {
cnt[get_val_block(v[i], nr_block)]++;
}
for (int i = 1; i <= RADIX_MASK; i++) {
psum[i] = psum[i - 1] + cnt[i - 1];
}
for (int i = 0; i < n; i++) {
next_v[psum[get_val_block(v[i], nr_block)]++] = v[i];
}
free(cnt);
free(psum);
}
void radix_sort(int *v, int n)
{
int *tmp = (int *)malloc(n * sizeof(int));
for (int i = 0; i < NR_CNT_SORTS; i++) {
count_sort(v, tmp, n, i);
memcpy(v, tmp, n * sizeof(int));
}
free(tmp);
}
int main()
{
freopen("radixsort.in", "r", stdin);
freopen("radixsort.out", "w", stdout);
int n, a, b, c;
scanf("%d%d%d%d", &n, &a, &b, &c);
int *v = (int *) malloc(n * sizeof(int));
v[0] = b;
for (int i = 1; i < n; i++) {
v[i] = (1LL * a * v[i - 1] + b) % c;
}
radix_sort(v, n);
for (int i = 0; i < n; i += 10) {
printf("%d ", v[i]);
}
printf("\n");
free(v);
}