Pagini recente » Cod sursa (job #3273245) | Cod sursa (job #308563) | Cod sursa (job #1534202) | Cod sursa (job #1735961) | Cod sursa (job #2126016)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("radixsort.in" );
ofstream g("radixsort.out");
int N;
int v[10000001];
vector<int> group[10];
void GenerateArray()
{
int A, B, C;
f >> N >> A >> B >> C;
v[1] = B;
for ( int i=2; i<=N; i++ )
v[i] = (A * v[i-1] + B) % C;
}
int Cif(int x, int pos) {
for ( int i=1; i<pos; i++ )
x /= 10;
return x%10;
}
int NrCif(int x)
{
int ncif = 0;
while ( x ) {
x/=10;
ncif++;
}
return ncif;
}
void RadixSort(int v[], int N)
{
int passes = 1;
for ( int i=1; i<=N; i++ )
passes = max(passes, NrCif(v[i]));
for ( int nPas=1; nPas<=passes; nPas++ )
{
for ( int i=1; i<=N; i++ )
group[Cif(v[i], nPas)].push_back(v[i]);
int k = 0;
for ( int j=0; j<=9; j++ ) {
for ( unsigned int i=0; i<group[j].size(); i++ )
v[++k] = group[j][i];
group[j].erase(group[j].begin(), group[j].end());
}
}
}
int main()
{
GenerateArray();
RadixSort(v, N);
for ( int i=0; i*10+1<=N; i++ )
g << v[i*10+1] << ' ';
}