Cod sursa(job #2375007)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 7 martie 2019 21:45:26
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#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 size, int byte)
{
    int index[1<<RADIX_WORD_SIZE];
    int freq[1<<RADIX_WORD_SIZE];

    memset(freq, 0, sizeof(freq));

    for(int i = 0; i < size; ++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 < size; ++i)
        sorted[ index[ GET_BYTE(unsorted[i], byte) ]++ ] = unsorted[i];
}

void sort_radix(int toSort[], int size)
{
    int *temp = new int[size];
    for(unsigned i = 0; i < TOTAL_BYTES; ++i)
        if(i&1)
            sort_count(temp, toSort, size, i);
        else
            sort_count(toSort, temp, size, i);
    delete[] temp;
}

int main()
{
    int N, A, B, C;
    in >> N >> A >> B >> C;

    int *numbers = new int[N];
    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] << ' ';

    delete[] numbers;

    return 0;
}