Pagini recente » Cod sursa (job #2929548) | Cod sursa (job #488894) | Cod sursa (job #3243892) | Cod sursa (job #761010) | Cod sursa (job #2676787)
#include <iostream>
#include <stdio.h>
#define NMAX 10000000
#define MAX_BITS 32
#define BITS_PAIR 8
#define MAXPAIRNR (1 << 8)
#define MASK (1 << 8) - 1
using namespace std;
int n;
int v[NMAX + 1], cv[NMAX + 1], f[MAXPAIRNR + 1], ind[MAXPAIRNR + 1];
void set_vector(int a, int b, int c) {
int i;
v[0] = b;
for (i = 1; i < n; i++)
v[i] = ((long long) a * v[i - 1] + b) % c;
}
void resetf() {
int i;
for (i = 0; i <= MAXPAIRNR; i++)
f[i] = 0;
}
void mysort(int bits) {
int i, max1, nr;
if (bits == MAX_BITS)
return;
resetf();
max1 = 0;
for (i = 0; i < n; i++) {
cv[i] = v[i];
nr = v[i] >> bits & MASK;
f[nr]++;
if (nr > max1)
max1 = nr;
}
ind[0] = 0;
for (i = 1; i <= max1; i++)
ind[i] = f[i - 1] + ind[i - 1];
for (i = 0; i < n; i++) {
nr = cv[i] >> bits & MASK;
v[ind[nr]] = cv[i];
ind[nr]++;
}
mysort(bits + BITS_PAIR);
}
int main() {
FILE *fin, *fout;
int a, b, c, i;
fin = fopen ("radixsort.in", "r");
fscanf(fin, "%d%d%d%d", &n, &a, &b, &c);
fclose( fin );
set_vector(a, b, c);
mysort(0);
fout = fopen("radixsort.out", "w");
for (i = 0; i < n; i += 10)
fprintf(fout, "%d ", v[i]);
fclose( fout );
return 0;
}