Pagini recente » Cod sursa (job #1976817) | Cod sursa (job #2212989) | Cod sursa (job #269874) | Cod sursa (job #734339) | Cod sursa (job #2434973)
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
vector<int> countingSort(vector<int> arr, int digitIndex)
{
int count[10];
memset(count, 0, sizeof count);
vector<int> result = arr;
for (int num : arr)
{
count[(num / digitIndex) % 10]++;
}
for (int i = 1; i < 10; i++)
{
count[i] += count[i - 1];
}
for (int i = arr.size() - 1; i >= 0; i--)
{
result[count[(arr[i] / digitIndex) % 10] - 1] = arr[i];
count[(arr[i] / digitIndex) % 10]--;
}
return result;
}
vector<int> radixSort(vector<int> arr)
{
int maxElem = *max_element(arr.begin(), arr.end());
for (int exp = 1; maxElem / exp > 0; exp *= 10)
{
arr = countingSort(arr, exp);
}
return arr;
}
int main()
{
int N, A, B, C;
fin >> N >> A >> B >> C;
vector<int> arr;
arr.push_back(B);
for (int i = 1; i < N; i++)
{
arr.push_back((arr.back() * A + B) % C);
}
arr = radixSort(arr);
for (int i = 0; i < N; i += 10)
{
fout << arr[i] << " ";
}
return 0;
}