Pagini recente » Cod sursa (job #399367) | Cod sursa (job #1594896) | Cod sursa (job #1400158) | Cod sursa (job #2219142) | Cod sursa (job #2741216)
#include <iostream>
#include <fstream>
int v[10000001];
void CountSort(int* v, int n, int exp, int* temp) {
int i;
int min = 9;
int max = 0;
int digit;
int count[10] = { 0 };
for (i = 0; i < n; ++i) {
digit = (v[i] / exp) % 10;
++count[digit];
if (digit < min)
min = digit;
if (digit > max)
max = digit;
}
for (i = min + 1; i <= max; ++i)
count[i] += count[i - 1];
int poz;
for (i = n - 1; i >= 0; --i) {
digit = (v[i] / exp) % 10;
poz = count[digit] - 1;
temp[poz] = v[i];
--count[digit];
}
for (i = 0; i < n; ++i)
v[i] = temp[i];
}
void RadixSort(int* v, int n) {
int max = 0;
for (int i = 0; i < n; ++i) {
if (v[i] > max)
max = v[i];
}
int* temp = new int[n];
for (int exp = 1; max / exp > 0; exp *= 10)
CountSort(v, n, exp, temp);
delete[] temp;
}
int main() {
std::ifstream fin("radixsort.in");
std::ofstream fout("radixsort.out");
int N, A, B, C;
fin >> N >> A >> B >> C;
v[0] = B;
int i;
for (i = 1; i < N; ++i)
v[i] = (A * v[i - 1] + B) % C;
RadixSort(v, N);
for (i = 0; i < N; i += 10)
fout << v[i] << ' ';
fin.close();
fout.close();
return 0;
}