Pagini recente » Cod sursa (job #3037830) | Cod sursa (job #2018734) | Cod sursa (job #696590) | Cod sursa (job #1731790)
#include <iostream>
#include <fstream>
using namespace std;
const int nmax = 10000001;
int a[nmax];
int n;
int A,B,C;
void counting(int digit);
void radixSort();
int main()
{
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
fin >> n;
fin >> A >> B >> C;
a[0] = B;
for(int i=1; i<n; i++)
{
a[i] = (A * a[i-1] + B) % C;
}
radixSort();
for(int i=0; i<n; i+=10)
{
fout << a[i] << " ";
}
fin.close();
fout.close();
return 0;
}
void radixSort()
{
int maxNumber = a[0];
for(int i=1 ; i<n; i++)
if(a[i] > maxNumber)
maxNumber = a[i];
for(int digit = 1; maxNumber/digit > 0; digit*= 10)
{
counting(digit);
}
}
void counting(int digit)
{
int temp[n];
int counts[10] = {0};
int i;
for(i=0; i<n; i++)
{
counts[(a[i]/digit)%10]++;
}
for(i=1; i<10; i++)
{
counts[i] +=counts[i-1];
}
for(i=n-1; i>=0; i--)
{
temp[counts[(a[i]/digit)%10]-1] = a[i];
counts[(a[i]/digit)%10]--;
}
for(i=0; i<n; i++)
{
a[i] = temp[i];
}
}