Cod sursa(job #2374911)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 7 martie 2019 21:15:04
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 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)
/*
inline int get_byte(int x, int byte)
{
    return (x>>(RADIX_WORD_SIZE * byte)&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+5) * 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);
    free(temp);
}

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

    int *numbers = (int*) malloc((N+5) * 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] << ' ';

    free(numbers);

    return 0;
}