Pagini recente » Profil nicolaefilat | Monitorul de evaluare | Cod sursa (job #2843956) | Politic2 | Cod sursa (job #2778614)
#include <fstream>
#include <vector>
#include <inttypes.h>
using namespace std;
#define FULL_BYTE (uint32_t) 0x000000ff
void radixsort(vector<uint32_t> &v) {
size_t n = v.size();
uint32_t *bucket = new uint32_t[n];
uint32_t count[FULL_BYTE + 1];
size_t i, j;
for (i = 0; i <= FULL_BYTE; i++)
count[i] = 0;
for (j = 0; j < 32; j += 8) {
for (i = 0; i < n; i++) {
uint32_t key = (v[i] >> j) & FULL_BYTE;
count[key]++;
}
for (i = 1; i <= FULL_BYTE; i++)
count[i] += count[i - 1];
// se face parcurgerea de la dreapta la stanga, ca sa pun in bucket mai
// intai numerele mai mari (dpdv al octetului curent) pe indici mai
// mari
for (long k = n - 1; k >= 0; --k) {
uint32_t key = (v[k] >> j) & FULL_BYTE;
// iar aici daca se intampla sa fie un numar w cu aceeasi cheie, va
// fi pus pe o pozitie mai mica; cel pus inaintea lui w era mai in
// dreapta in vector, deci mai mare dpdv al octetilor mai putini
// semnificativi decat cel de la pasul curent
bucket[--count[key]] = v[k];
}
for (i = 0; i <= FULL_BYTE; i++)
count[i] = 0;
for (i = 0; i < n; i++)
v[i] = bucket[i];
}
delete[] bucket;
}
int main(void) {
ifstream in("radixsort.in");
ofstream out("radixsort.out");
uint32_t n, a, b, c, i;
in >> n >> a >> b >> c;
vector<uint32_t> v(n);
v[0] = b;
for (i = 1; i < n; i++)
v[i] = (uint32_t) ((1UL * a * v[i - 1] + b * 1UL) % c);
radixsort(v);
for (i = 0; i < n; i += 10)
out << v[i] << ' ';
in.close();
out.close();
return 0;
}