Pagini recente » Cod sursa (job #821696) | Cod sursa (job #2009342) | Cod sursa (job #2125008) | Cod sursa (job #2019300) | Cod sursa (job #1457147)
#include <fstream>
#include <string.h>
using namespace std;
#define Nmax 10000000
#define NR_BYTES (sizeof(x[0]))
#define BYTE 0xFF
#define getByte(x) ( ((x) >> (8 * byte)) & BYTE )
int x[Nmax], y[Nmax];
int counter[BYTE], index[BYTE];
int* radixSort(int) ;
void countSort(int*, int*, int, int) ;
int main()
{
freopen("radixsort.in", "r", stdin);
freopen("radixsort.out", "w", stdout);
int i, n, A, B, C;
int *v;
scanf("%d %d %d %d", &n, &A, &B, &C);
for(x[0] = B, i = 1; i < n; ++i)
x[i] = (A * x[i - 1] + B) % C;
v = radixSort(n);
for(i = 0; i < n; i += 10) printf("%d ", v[i]);
printf("\n");
return 0;
}
int* radixSort(int n)
{
int i;
int *v1 = x, *v2 = y;
for(i = 0; i < NR_BYTES; ++i)
{
countSort(v1, v2, n, i);
swap(v1, v2);
}
return v1;
}
void countSort(int v1[], int v2[], int n, int byte)
{
int i;
memset(counter, 0, sizeof(counter));
for(i = 0; i < n; ++i) counter[ getByte(v1[i]) ]++;
for(i = 1; i < BYTE; ++i) index[i] = index[i - 1] + counter[i - 1];
for(i = 0; i < n; ++i)
v2[ index[ getByte(v1[i]) ]++ ] = v1[i];
}