Pagini recente » Cod sursa (job #349521) | Cod sursa (job #1970624) | Cod sursa (job #2561762) | Cod sursa (job #2672623) | Cod sursa (job #2375012)
#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)
void sort_count(int *unsorted, int *sorted, int N, 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 *numbers, int N)
{
int *temp = (int*) malloc(N * sizeof(int));
for(unsigned i = 0; i < TOTAL_BYTES; ++i)
if(i&1)
sort_count(temp, numbers, N, i);
else
sort_count(numbers, temp, N, i);
}
int main()
{
int N, A, B, C;
in >> N >> A >> B >> C;
int *numbers = (int*) malloc(N * sizeof(int));
numbers[0] = B % C;
for(int i = 1; i < N; ++i)
numbers[i] = (1LL * A * numbers[i-1] % C + B) % C;
sort_radix(numbers, N);
for(int i = 0; i < N; i += 10)
out << numbers[i] << ' ';
return 0;
}