Pagini recente » Cod sursa (job #2982879) | Cod sursa (job #2894230) | Cod sursa (job #846046) | Cod sursa (job #1889992) | Cod sursa (job #2741592)
#include <iostream>
#include <fstream>
int v[10000001];
void CountingSort(int* v, int n, int exp, int* temp) {
int i;
int count[10] = { 0 };
for (i = 0; i < n; ++i)
++count[(v[i] / exp) % 10];
for (i = 1; i <= 9; ++i)
count[i] += count[i - 1];
for (i = n - 1; i >= 0; --i) {
temp[count[(v[i] / exp) % 10] - 1] = v[i];
--count[(v[i] / exp) % 10];
}
}
void RadixSort(int* v, int n) {
int i;
int max = 0;
for (i = 0; i < n; ++i) {
if (v[i] > max)
max = v[i];
}
int j;
int* temp = new int[n];
for (i = 1, j = 0; max / i > 0; i *= 10, ++j) {
if (j % 2 == 0)
CountingSort(v, n, i, temp);
else
CountingSort(temp, n, i, v);
}
if (j % 2 == 1)
CountingSort(temp, n, i, v);
delete[] temp;
}
int main() {
std::ifstream fin("radixsort.in");
std::ofstream fout("radixsort.out");
int N, A, B, C;
fin >> N >> A >> B >> C;
fin.close();
v[0] = B;
int i;
for (i = 1; i < N; ++i)
v[i] = (1LL * A * v[i - 1] + B) % C;
RadixSort(v, N);
for (i = 0; i < N; i += 10)
fout << v[i] << ' ';
fout.close();
return 0;
}