Pagini recente » Cod sursa (job #860784) | Cod sursa (job #767299) | Cod sursa (job #1515604) | Cod sursa (job #155500) | Cod sursa (job #2374939)
#include <fstream>
#include <cstring>
using namespace std;
#define FILE_NAME "radixsort"
ifstream in (FILE_NAME".in");
ofstream out(FILE_NAME".out");
#define RADIX_MASK 0xFF
#define RADIX_WORD_SIZE 8
#define TOTAL_BYTES sizeof(int)
#define GET_BYTE(x, b) (x>>(RADIX_WORD_SIZE * b)%RADIX_MASK)
const int MAX_DIM = 10000000 + 16;
int numbers[MAX_DIM];
int N;
void sort_count(int *unsorted, int *sorted, int byte)
{
int index[1<<RADIX_WORD_SIZE];
int freq[1<<RADIX_WORD_SIZE];
memset(freq, 0, sizeof(freq));
for(int i = 0; i < N; ++i)
++freq[ GET_BYTE(unsorted[i], byte) ];
index[0] = 0;
for(int i = 1; i < (1 << RADIX_WORD_SIZE); ++i)
index[i] = index[i-1] + freq[i-1];
for(int i = 0; i < N; ++i)
sorted[ index[ GET_BYTE(unsorted[i], byte) ]++ ] = unsorted[i];
/// dont forget that ++ !!
}
void sort_radix()
{
int *temp = new int[N];
for(unsigned i = 0; i < TOTAL_BYTES; ++i)
if(i&1)
sort_count(temp, numbers, i);
else
sort_count(numbers, temp, i);
}
int main()
{
int A, B, C;
in >> N >> A >> B >> C;
numbers[0] = B % C;
for(int i = 1; i < N; ++i)
numbers[i] = (1LL * A * numbers[i-1] % C + B) % C;
sort_radix();
for(int i = 0; i < N; i += 10)
out << numbers[i] << ' ';
return 0;
}