Pagini recente » Cod sursa (job #1987049) | Cod sursa (job #831525) | Cod sursa (job #2480730) | Cod sursa (job #1981231) | Cod sursa (job #1213512)
#include<cstdio>
#include<algorithm>
#include<queue>/*folosesc 255 de cozi*/
#define N 10000003
using namespace std;
unsigned int n, A, B, C, v[N], k, first=255, second=65280, third=16711680, fourth=4278190080;
queue<int> Q[2][256];
void genereaza()
{
v[1] = B;
for(int i=2; i<=n; i++)
v[i] = (long long)((long long)A * v[i-1] + B) % C;
}
void afiseaza()
{
for(int i=1; i<=n; i+=10)
printf("%d ",v[i]);
}
void radix()
{
int i, bit=8, nr;
k = 0;
/*sortez dupa primul byte*/
for(i=1; i<=n; i++)
Q[ k ][ v[i]&first ].push(v[i]);
/*sortez dupa al doilea byte*/
for(i=0; i<=255; i++)
while(!Q[k][i].empty())
{
nr = Q[k][i].front();
Q[ 1-k ][ (nr&second)>>8 ].push(nr);
Q[k][i].pop();
}
k=1-k;
/*sortez dupa al treilea byte*/
for(i=0; i<=255; i++)
while(!Q[k][i].empty())
{
nr = Q[k][i].front();
Q[ 1-k ][ (nr&third)>>16 ].push(nr);
Q[k][i].pop();
}
k=1-k;
/*sortez dupa al patrulea byte*/
for(i=0; i<=255; i++)
while(!Q[k][i].empty())
{
nr = Q[k][i].front();
Q[ 1-k ][ (nr&fourth)>>24 ].push(nr);
Q[k][i].pop();
}
k=1-k;
nr=0;
/*pun numerele in vector*/
for(i=0; i<=255; i++)
while(!Q[k][i].empty())
{
v[++nr] = Q[k][i].front();
Q[k][i].pop();
}
}
int main()
{
/*v[1] = B
v[i] = (A * v[i-1] + B) % C*/
freopen("radixsort.in","r",stdin);
freopen("radixsort.out","w",stdout);
scanf("%d %d %d %d",&n, &A, &B, &C);
genereaza();
radix();
afiseaza();
/*std::sort(v+1, v+n+1);
printf("\n");
afiseaza();*/
return 0;
}