Pagini recente » Cod sursa (job #3318151) | Cod sursa (job #3299809) | Cod sursa (job #548870) | Cod sursa (job #2395576) | Cod sursa (job #3346554)
#include <iostream>
#define NMAX 10000000
#define RADIX 16
// linked list implementation
void linked_count_sort(int *v, int n, int radix, int base)
{
int digit;
int head[RADIX];
int next[NMAX];
int w[NMAX];
for (int i = 0; i < radix; ++i)
head[i] = -1;
for (int i = 0; i < n; ++i)
next[i] = -1;
for (int i = 0, j; i < n; ++i) {
digit = (v[i] / base) % radix;
if (head[digit] == -1) {
head[digit] = i;
} else {
j = head[digit];
while (next[j] != -1)
j = next[j];
next[j] = i;
}
}
for (int k = 0, digit = 0; digit <= 9; ++digit)
for (int j = head[digit]; j != -1; j = next[j])
w[k++] = v[j];
for (int i = 0; i < n; ++i)
v[i] = w[i];
}
void naive_count_sort(int *v, int n, int radix, int base)
{
int w[NMAX];
for (int k = 0, digit = 0; digit <= 9; ++digit)
for (int i = 0; i < n; ++i)
if ((v[i] / base) % radix == digit)
w[k++] = v[i];
for (int i = 0; i < n; ++i)
v[i] = w[i];
}
void count_sort(int *v, int n, int radix, int base)
{
int count[RADIX];
int index[RADIX];
int w[NMAX];
for (int digit = 0; digit < radix; ++digit)
count[digit] = 0;
for (int i = 0; i < n; ++i)
++count[(v[i] / base) % radix];
index[0] = 0;
for (int digit = 1; digit < radix; ++digit)
index[digit] = index[digit - 1] + count[digit - 1];
for (int i = 0; i < n; ++i)
w[index[(v[i] / base) % radix]++] = v[i];
for (int i = 0; i < n; ++i)
v[i] = w[i];
}
void radix_sort(int *v, int n, int radix)
{
int max;
max = v[0];
for (int i = 1; i < n; ++i)
if (v[i] > max)
max = v[i];
for (int base = 1; base <= max && base != 0; base *= radix)
count_sort(v, n, radix, base);
}
int main()
{
int n, a, b, c;
int v[NMAX];
freopen("radixsort.in", "r", stdin);
freopen("radixsort.out", "w", stdout);
std::cin >> n >> a >> b >> c;
v[0] = b;
for (int i = 1; i < n; ++i)
v[i] = (a * v[i - 1] + b) % c;
radix_sort(v, n, RADIX);
for (int i = 0; i < n; i += 10)
std::cout << v[i] << ' ';
std::cout << '\n';
return 0;
}