Pagini recente » Cod sursa (job #117097) | Cod sursa (job #1009550) | Cod sursa (job #2614740) | Cod sursa (job #2617078) | Cod sursa (job #1774734)
#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;
ifstream f ("radixsort.in");
ofstream g ("radixsort.out");
const int BITS = 8;
const int MASK = (1 << BITS) - 1;
int n, a[10000001], A, B, C;
void afisare (int a[], int n)
{
for (int i = 1; i <= n; i += 10)
g << a[i] << ' ';
}
void selectionsort (int in, int sf)
{
int i, j, k, tmp;
for (i = in; i < sf; i++)
{
k = i;
for (j = k + 1; j < sf; j++)
{
if (a[j] < a[k])
k = j;
}
tmp = a[i];
a[i] = a[k];
a[k] = tmp;
}
}
void radixsort (int in, int sf, int bits)
{
int prim[1 << BITS], ultim[1 << BITS];
for (int i = 0; i < (1 << BITS); i++)
ultim[i] = 0;
for (int i = in; i < sf; i++)
ultim[ (a[i] >> bits) & MASK]++;
prim[0] = in;
ultim[0] += in;
for (int i = 1; i < (1 << BITS); i++)
{
prim[i] = ultim[i - 1];
ultim[i] += ultim[i - 1];
}
for (int i = 0; i < (1 << BITS); i++)
{
while (prim[i] != ultim[i])
{
int elem = a[prim[i]];
int bucket = (elem >> bits) & MASK;
while (bucket != i)
{
int tmp = a[prim[bucket]];
a[prim[bucket]++] = elem;
elem = tmp;
bucket = (elem >> bits) & MASK;
}
a[prim[i]++] = elem;
}
}
if (bits)
{
for (int i = 0; i < (1 << BITS); i++)
{
int lg = ultim[i] - (i ? ultim[i - 1] : in);
if (lg > 64)
{
radixsort (ultim[i] - lg, ultim[i], bits - BITS);
}
else if (lg > 1)
{
selectionsort (ultim[i] - lg, ultim[i]);
}
}
}
}
int main()
{
f >> n >> A >> B >> C;
a[1] = B;
for (int i = 2; i <= n; i++)
{
a[i] = (1LL * A * a[i - 1] + B) % C;
}
radixsort (1, n+1, 24);
afisare (a, n);
return 0;
}