Pagini recente » Cod sursa (job #33134) | Cod sursa (job #1220721) | Cod sursa (job #745414) | Cod sursa (job #507438) | Cod sursa (job #1837976)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define BUCKETS 256 // 1 bucket de 8 biti
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
void RadixSort(vector<int> &V){
int Mask = BUCKETS - 1; // 255 = 1111 1111
int N = V.size();
vector<int> Cnt, Sol;
Cnt.resize(BUCKETS);
Sol.resize(V.size());
// sortez pe bucati de 8 biti
for (int i = 0; i < 32; i += 8) {
fill(Cnt.begin(), Cnt.end(), 0); //folosesc count sort
// adaug fiecare numar la codul corespunzator
for (int j = 0; j < N; ++j)
Cnt[(V[j] >> i) & Mask]++;
// sume partiale pe vectorul de frecventa pentru a determina pozitiile elementelor in vector
for (int j = 1; j < BUCKETS; ++j)
Cnt[j] += Cnt[j-1];
// iau numerele si le rearanjez
for (int j = N-1; j >= 0; --j)
Sol[--Cnt[(V[j] >> i) & Mask]] = V[j];
// mut elementele in vectorul meu
copy(Sol.begin(), Sol.end(), V.begin());
}
}
int main(){
vector<int> V;
int N, A, B, C;
// citire
fin >> N >> A >> B >> C;
V.resize(N);
V[0] = B;
// creez vectorul dupa formula data
for (int i = 1; i < N; ++i)
V[i] = (1LL * V[i - 1] * A + B) % C;
// sortez vectorul prin metoda RadixSort
RadixSort(V);
// afisare
for (int i = 0; i < N; i += 10)
fout << V[i] << " ";
return 0;
}