Pagini recente » Cod sursa (job #2698843) | Cod sursa (job #1495569) | Cod sursa (job #42420) | Cod sursa (job #1320643) | Cod sursa (job #2674570)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");
int v[10000001];
int n;
struct nod
{
int info;
nod * urm;
nod * prev;
}*p[260], *u[260];
int countDigits(int x)
{
int nr=0;
while(x!=0) nr++, x/=256;
return nr;
}
int getMaxValue(int v[])
{
int mx=v[1];
for(int i=2; i<=n; i++)
{
if(v[i]>mx) mx=v[i];
}
return mx;
}
void adaug(int i, int x)
{
nod * aux = new nod;
aux->info=x;
aux->prev=NULL;
aux->urm=p[i];
if(p[i]!=NULL)p[i]->prev=aux;
p[i]=aux;
if(u[i]==NULL)
{
u[i]=aux;
}
}
void radixSort(int v[])
{
int steps=countDigits(getMaxValue(v));
int power=1;
int i, k;
for(k=1; k<=steps; k++)
{
for(i=0; i<256; i++)
{
u[i]=NULL;
p[i]=NULL;
}
for(i=1; i<=n; i++)
{
adaug(v[i]/power%256, v[i]);
}
n=0;
for(i=0; i<256; i++)
{
while(u[i]!=NULL)
{
v[++n]=u[i]->info;
nod * sterg=u[i];
u[i]=u[i]->prev;
delete sterg;
}
}
power*=256;
}
}
int main()
{
int a, b, c;
fin>>n>>a>>b>>c;
v[1]=b%c;
for(int i=2; i<=n; i++)
{
v[i]=(1LL*a*v[i-1]%c+b)%c;
}
//sort(v+1, v+n+1);
radixSort(v);
for(int i=1; i<=n; i+=10) fout<<v[i]<<' ';
}