Cod sursa(job #1457149)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 2 iulie 2015 19:49:40
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <string.h>
using namespace std;
#define Nmax 10000000
#define NR_BYTES (sizeof(x[0]))
#define BYTE 0xFF

#define getByte(x) ( ((x) >> (8 * byte)) & BYTE )

int x[Nmax], y[Nmax];

int* radixSort(int) ;
void countSort(int*, int*, int, int) ;

int main()
{
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    
    int i, n, A, B, C;
    int *v;
    
    scanf("%d %d %d %d", &n, &A, &B, &C);
    
    for(x[0] = B, i = 1; i < n; ++i)
        x[i] = (A * x[i - 1] + B) % C;
    
    v = radixSort(n);
    
    for(i = 0; i < n; i += 10) printf("%d ", v[i]);
    
    printf("\n");
    
    return 0;
}

int* radixSort(int n)
{
    int i;
    int *v1 = x, *v2 = y;
    
    for(i = 0; i < NR_BYTES; ++i)
    {
        countSort(v1, v2, n, i);
        
        swap(v1, v2);
    }
    
    return v1;
}


void countSort(int v1[], int v2[], int n, int byte)
{
    int i;
    int counter[BYTE], index[BYTE];
    
    memset(counter, 0, sizeof(counter));
    
    for(i = 0; i < n; ++i) counter[ getByte(v1[i]) ]++;
    for(index[0] = 0, i = 1; i < BYTE; ++i) index[i] = index[i - 1] + counter[i - 1];
    
    for(i = 0; i < n; ++i)
        v2[ index[ getByte(v1[i]) ]++ ] = v1[i];
}