Pagini recente » Cod sursa (job #730736) | Cod sursa (job #2448170) | Cod sursa (job #1777384) | Istoria paginii runda/riad | Cod sursa (job #1458302)
#include <fstream>
#include <iostream>
using namespace std;
ofstream fout("radixsort.out");
ifstream fin("radixsort.in");
const int NMAX = 10000005;
const int MASK = (1 << 8) - 1; // 255
int n, A, B, C, key;
int v [NMAX], aux [NMAX], bucket [MASK + 2];
void Citire()
{
fin >> n >> A >> B >> C;
v[1] = B;
int i ;
for ( i = 2 ; i <= n ; ++ i )
{
v [i] = ( 1LL * A * v [i-1] + B ) % C ; // 1LL = conversie in long long
}
}
void Radix_Sort()
{
for ( int shift = 0 ; shift < 32 ; shift += 8 ) // 4pasi
{
for ( int i = 1 ; i <= n ; ++ i )
{
key = ( v[i] >> shift ) & MASK ; // mascare binară
++ bucket [ key ] ;
}
for ( int i = 0 ; i <= MASK ; ++ i )
{
bucket [i] += bucket [i - 1] ;
}
for ( int i = n ; i ; -- i )
{
key = ( v[i] >> shift ) & MASK; // mascare binară
aux [bucket[key]--] = v[i];
}
for ( int i = 1 ; i <= n ; ++ i)
{
v [i] = aux [i];
}
for ( int i = 1 ; i <= MASK ; ++ i )
{
bucket[i] = 0;
}
}
}
void Afisare()
{
for ( int i = 1 ; i <= n ; i += 10 )
fout << v[i] << ' ';
}
int main()
{
Citire ();
Radix_Sort ();
Afisare ();
fout.close();
fin.close();
return 0;
}