Pagini recente » Cod sursa (job #51935) | Cod sursa (job #2917413) | Cod sursa (job #1116200) | Cod sursa (job #1247017) | Cod sursa (job #1198517)
#include <fstream>
#include <vector>
using namespace std;
const int bytes = sizeof(int);
const int bucketSize = 32 / bytes;
const int radixSize = 1 << bucketSize;
const int mask = radixSize - 1;
int N, A, B, C;
vector<int> v;
inline int getByte(int n, int shift) {
return (n >> shift) & mask;
}
void countSort(vector<int> &a, vector<int> &b, int byte) {
vector<int> cnt(radixSize, 0);
for (int i = 0; i < N; ++i)
++cnt[getByte(a[i], byte * bucketSize)];
for (int i = 1; i < radixSize; ++i)
cnt[i] += cnt[i - 1];
for (int i = N - 1; i + 1; --i)
b[--cnt[getByte(a[i], byte * bucketSize)]] = a[i];
}
void radixSort(vector<int> &v) {
vector<int> aux(N, 0);
for (int i = 0; i < 4; ++i)
if (i & 1) {
countSort(aux, v, i);
} else {
countSort(v, aux, i);
}
}
void generateArray(vector<int> &v) {
v.resize(N), v[0] = B;
for (int i = 1; i < N; ++i)
v[i] = (1LL * A * v[i - 1] + B) % C;
}
int main() {
ifstream f("radixsort.in");
ofstream g("radixsort.out");
f >> N >> A >> B >> C;
generateArray(v);
radixSort(v);
for (int i = 0; i < N; i += 10)
g << v[i] << " ";
}