Cod sursa(job #1471171)

Utilizator EpictetStamatin Cristian Epictet Data 13 august 2015 13:04:06
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <cstring>

#define Radix_Size 8  /// Inpart in 4 bucati de cate 8 biti;
#define Total_Bytes 4 /// int;
#define Radix 0xFF   /// Are valoarea 255 pe int adica 24 de zero si 8 de unu in reprezentare;

using namespace std;

ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");

int n, a, b, c, *V;

void Read()
{
    fin >> n >> a >> b >> c;
    V = new int[n]();
    V[0] = b;
    for (int i = 1; i < n; i ++)
    {
        V[i] = (1LL * a * V[i - 1] + b) % c;
    }
    fin.close();
}

void Write()
{
    for (int i = 0; i < n; i += 10)
    {
        fout << V[i] << ' ';
    }
    fout << '\n';
    fout.close();
}

inline int Get_Nr_From(int x, int &byte)
{
    return ((x >> (byte * Radix_Size) & Radix)); /// Returneaza numarul de 1 byte;
}

void Count_Sort(int A[], int B[], int byte)
{
    int counter[1 << Radix_Size];
    int index[1 << Radix_Size];

    memset(counter, 0, sizeof(counter));

    for (int i = 0; i < n; i++)
    {
        counter[Get_Nr_From(A[i], byte)] ++;
    }

    index[0] = 0;
    for (int i = 1; i < (1 << Radix_Size); i++)
    {
        index[i] = index[i - 1] + counter[i - 1];
    }

    for (int i = 0; i < n; i++)
    {
        B[index[Get_Nr_From(A[i], byte)]++] = A[i];
    }
}

void Radix_Sort()
{
    int *temp = new int[n]();
    for (int i = 0; i < Total_Bytes; i ++)
    {
        if (i % 2 == 0)
        {
            Count_Sort(V, temp, i);
        }
        else
        {
            Count_Sort(temp, V, i);
        }
    }
}

int main()
{
    Read();
    Radix_Sort();
    Write();

    return 0;
}