Pagini recente » Cod sursa (job #1022066) | Cod sursa (job #746272) | Cod sursa (job #1056225) | Cod sursa (job #1014834) | Cod sursa (job #1419581)
#include <stdio.h>
#define MAX_N 10000000
#define BITS 8
#define MASK ((1 << BITS) - 1)
#define THRESHOLD 64
#define MAX_DIG 10
#define BUFF_SIZE 4096
int v[MAX_N];
char buff[BUFF_SIZE], dig[MAX_DIG];
int pos;
inline void insertionSort(int lo, int hi) {
for (int i = lo; i < hi; i++) {
// insereaza v[i] in v[lo..i]
int x = v[i];
int j = i;
while ((j > lo) && (v[j - 1] > x)) {
v[j] = v[j - 1];
j--;
}
v[j] = x;
}
}
void radixSort(int lo, int hi, int bits) {
int ptr[1 << BITS], end[1 << BITS] = { };
for (int i = lo; i < hi; i++) {
end[(v[i] >> bits) & MASK]++;
}
// deplasement
ptr[0] = lo;
end[0] += lo;
for (int i = 1; i < (1 << BITS); i++) {
ptr[i] = end[i - 1];
end[i] += end[i - 1];
}
for (int i = 0; i < (1 << BITS); i++) {
while (ptr[i] != end[i]) {
int elem = v[ptr[i]];
int bucket = (elem >> bits) & MASK;
while (bucket != i) {
int tmp = v[ptr[bucket]];
v[ptr[bucket]++] = elem;
elem = tmp;
bucket = (elem >> bits) & MASK;
}
v[ptr[i]++] = elem;
}
}
if (bits) {
for (int i = 0; i < (1 << BITS); i++) {
int size = end[i] - (i ? end[i - 1] : lo);
if (size > THRESHOLD) {
radixSort(end[i] - size, end[i], bits - BITS);
} else if (size > 1) {
insertionSort(end[i] - size, end[i]);
}
}
}
}
inline void put(FILE *f, char c) {
buff[pos++] = c;
if (pos == BUFF_SIZE) {
fwrite(buff, 1, BUFF_SIZE, f);
pos = 0;
}
}
inline void write(FILE *f, int x) {
int nDig = 0;
do {
int q = x / 10;
dig[nDig++] = x - (q << 1) - (q << 3) + '0';
x = q;
} while (x);
while (nDig--) {
put(f, dig[nDig]);
}
}
int main(void) {
FILE *f;
int n;
int a, b, c;
f = fopen("radixsort.in", "r");
fscanf(f, "%d%d%d%d", &n, &a, &b, &c);
fclose(f);
v[0] = b;
for (int i = 1; i < n; i++) {
long long temp = 1LL * v[i - 1] * a + b;
v[i] = temp - (temp / c) * c;
}
radixSort(0, n, 24);
f = fopen("radixsort.out", "w");
for (int i = 0; i < n; i += 10) {
write(f, v[i]);
put(f, ' ');
}
if (pos) {
fwrite(buff, 1, pos, f);
}
fclose(f);
return 0;
}