Pagini recente » Cod sursa (job #3219924) | Cod sursa (job #422059) | Cod sursa (job #2600832) | Cod sursa (job #1658343) | Cod sursa (job #1456638)
#include <fstream>
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;
for(int 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) { // 4 pași
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 afis()
{
for(int i=1; i<=n; i+=10)
fout << v[i] << ' ';
}
int main()
{
citire();
radix_sort();
afis();
fout.close();
fin.close();
return 0;
}