Pagini recente » Cod sursa (job #357852) | Cod sursa (job #3198530) | Cod sursa (job #1572176) | Cod sursa (job #2183576) | Cod sursa (job #2617540)
#include <fstream>
#define N 10000001
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
int n,b,a,c;
long long v[N],auxiliar[N];
const int RADIX=255;
long long ElementulMaxim(long long v[], int n)
{
long long maxi = v[0];
for (int i = 1; i < n; i++)
if (v[i] > maxi)
maxi = v[i];
return maxi;
}
void CountSortRadix(long long v[], int n, int exp)
{
int i, numara[32] = {0};
/// Tinem minte numarul de aparitii in vectorul numara
for (i = 0; i < n; i++)
numara[(v[i] / exp) % 32]++;
/// Modificam numara[i] astfel incat numara[i] sa contina pozitia cifrei din auxiliar[]
for (i = 1; i < 32; i++)
numara[i] += numara[i - 1];
/// Creem vectorul auxiliar
for (i = n - 1; i >= 0; i--)
{
auxiliar[numara[(v[i] / exp) % 32] - 1] = v[i];
numara[(v[i] / exp) % 32]--;
}
/// Copiem continutul vectorului auxiliar[] in v[]
for (i = 0; i < n; i++)
v[i] = auxiliar[i];
}
/// Radix Sort
void radixsort(long long v[], long long w[], int n)
{
/// Calculam cel mai mare element pentru a afla numarul de cifre al acestuia
long long m = ElementulMaxim(v, n);
///Folosim Counting Sort pentru fiecare cifra
for (int exp = 1; m / exp > 0; exp *= 32)
CountSortRadix(v, n, exp);
}
/// RadixSort cu operatii pe biti
void CountSortRadixBiti(long long v[], int n, int byte)
{
int i;
int numara[256];
int pozitie[256];
for (i = 0; i < 256; i++)
numara[i] = 0;
for (int i = 0; i < n; i++)
++numara[(v[i] >> byte) & RADIX];
pozitie[0] = 0;
for (int i = 1; i < 256; i++)
pozitie[i] = pozitie[i - 1] + numara[i - 1];
for (int i = 0; i < n; i++)
auxiliar[pozitie[(v[i] >> byte) & RADIX]++] = v[i];
for (int i = 0; i < n; i++)
v[i] = auxiliar[i];
}
void RadixSortBiti(long long v[], int n)
{
for (int i = 0; i < 32; i += 8)
CountSortRadixBiti(v, n, i);
}
int main()
{
fin>>n>>a>>b>>c;
v[0]=b;
for(int i=1;i<n;++i)
{
v[i]=(a*v[i-1]+b)%c;
}
RadixSortBiti(v,n);
for(int i=0;i<n;i+=10)
fout<<v[i]<<" ";
return 0;
}