Pagini recente » Cod sursa (job #2725469) | Cod sursa (job #1256591) | Cod sursa (job #2451087) | Cod sursa (job #884247) | Cod sursa (job #2851045)
#include <bits/stdc++.h>
using namespace std;
ifstream in("radixsort.in");
ofstream out("radixsort.out");
const int Nmax = 1e7 + 5;
int N, a, b, c;
int v[Nmax];
const int BYTES = sizeof(v[0]);
const int BLOCK_SIZE = 0xFF;
const int BITB_SIZE = 8;
inline int get_byte(int x, int byte)
{
return (x >> (byte * 8) & BLOCK_SIZE);
}
void count_sort(int *A, int *B, int byte)
{
int counter[(1 << BITB_SIZE)];
int index[(1 << BITB_SIZE)];
memset(counter, 0, sizeof(counter));
for(int i = 0; i < N; ++i)
{
counter[get_byte(A[i], byte)]++;
}
index[0] = 0;
for(int i = 1; i < (1 << BITB_SIZE); ++i)
{
index[i] = index[i - 1] + counter[i - 1];
}
int byte_curr;
for(int i = 0; i < N; ++i)
{
byte_curr = get_byte(A[i], byte);
B[index[byte_curr]++] = A[i];
}
}
void radix_sort()
{
int *aux = new int [N + 1];
/*for(int i = 0; i < N; ++i)
{
cout << aux[i] << " ";
}*/
/*
de ce numai elementele de la aux[2] incolo sunt 0?
*/
for(int i = 0; i < BYTES; ++i)
{
if(i % 2 == 0)
{
count_sort(v, aux, i);
}
else
{
count_sort(aux, v, i);
}
}
}
int main()
{
in >> N >> a >> b >> c;
v[0] = b;
for(int i = 1; i < N; ++i)
{
v[i] = (1LL * a * v[i - 1] + b) % c;
}
radix_sort();
for(int i = 0; i < N; i += 10)
{
out << v[i] << " ";
}
return 0;
}