Pagini recente » Cod sursa (job #714411) | Cod sursa (job #1969168) | Cod sursa (job #1927276) | Cod sursa (job #3149988) | Cod sursa (job #2741198)
#include <iostream>
#include <fstream>
void CountSort(int* v, int n, int exp) {
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* out = new int[n];
int poz;
for (i = n - 1; i >= 0; --i) {
digit = (v[i] / exp) % 10;
poz = count[digit] - 1;
out[poz] = v[i];
--count[digit];
}
for (i = 0; i < n; ++i)
v[i] = out[i];
delete[] out;
}
void RadixSort(int* v, int n) {
int i;
int max = 0;
for (i = 0; i < n; ++i) {
if (v[i] > max)
max = v[i];
}
for (i = 1; max / i > 0; i *= 10)
CountSort(v, n, i);
}
int v[10000001];
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;
}