Pagini recente » Cod sursa (job #3267743) | Cod sursa (job #2035003) | Cod sursa (job #2532130) | Cod sursa (job #883037) | Cod sursa (job #2553168)
#include <fstream>
using namespace std;
ifstream cin("radixsort.in");
ofstream cout("radixsort.out");
void generare(int v[], int n, int A, int B, int C)
{
int i;
v[1] = B;
for(i = 2; i <= n; i ++)
v[i] = (A * v[i-1] + B) % C;
}
void afisare(int v[], int n)
{
int i = 1;
while(i <= n)
{
cout<<v[i]<<" ";
i += 10;
}
}
void countSort(int v[], int n, int maxi, int exp)
{
int frecv[10] = {0}, result[n+1], ind = 0, i, j;
for(i = 1; i <= n ; i ++)
frecv[ (v[i]/exp)%10 ] += 1;
for(i = 1; i < 10; i++)
frecv[i] += frecv[i-1]; //in frecv[i] vom avea pozitia fiecarei cifre in rezultat, poz = cate au fost pana la element + cate sunt ca el
for(i = n ; i >= 1; i --)
{
result[frecv[(v[i]/exp)%10]] = v[i];
frecv[ (v[i]/exp)%10 ] --;
}
for (i = 1; i <= n; i++)
v[i] = result[i];
}
void RadixSort(int v[], int n, int maxi)
{
int i,copymaxi = maxi,exp = 0, p10;
while(copymaxi > 0)
{
exp += 1;
copymaxi = copymaxi / 10;
}
i = 1;
p10 = 1;
while( i <= exp )
{
countSort(v,n,maxi,p10);
p10 = p10 * 10;
i += 1;
}
}
int main()
{
int maxi=0, n, i, A, B, C;
cin>>n>>A>>B>>C;
int v[n + 1],result[n + 1];
generare(v,n,A,B,C);
for(i = 1; i<=n; i++)
if(v[i] > maxi)
maxi = v[i];
RadixSort(v, n, maxi);
afisare(v,n);
return 0;
}