Pagini recente » Cod sursa (job #3243004) | Cod sursa (job #1674982) | Cod sursa (job #1317906) | Cod sursa (job #2974916) | Cod sursa (job #2586834)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
const int bucket = 255; // 2^8 - 1
inline int getByte(const int &no, const int &byte) {
return ((no >> (8 * byte)) & bucket);
}
inline void byteSort(vector <int> &Arr, vector <int> &aux, const int &byte) {
vector <int> counter(1 + bucket);
vector <int> index(1 + bucket);
for (int idx = 0; idx < (int)Arr.size(); ++idx)
++counter[getByte(Arr[idx], byte)];
for (int val = 1; val <= bucket; ++val)
index[val] = index[val - 1] + counter[val - 1]; // cu val - 1 in loc de val algoritmul devine stable
for (int idx = 0; idx < (int)Arr.size(); ++idx)
aux[index[getByte(Arr[idx], byte)]++] = Arr[idx]; // functioneaza pt ca e indexat de la 0
}
inline void RadixSort(vector <int> &Arr) {
vector <int> aux((int)Arr.size());
for (int byte = 0; byte < 4; ++byte) // int are 4 bytes
if(byte % 2 == 0)
byteSort(Arr, aux, byte); // sortez dupa byte-ul byte
else byteSort(aux, Arr, byte);
}
int main() {
int n, a, b, c;
fin >> n >> a >> b >> c;
vector <int> Arr(n);
Arr[0] = b;
for (int idx = 1; idx < n; ++idx)
Arr[idx] = (1LL * a * Arr[idx - 1] + b) % c;
//sort(Arr.begin(), Arr.end());
RadixSort(Arr);
for (int idx = 0; idx < n; idx += 10)
fout << Arr[idx] << ' ';
}