Cod sursa(job #1528265)

Utilizator kassay_akosKassay Akos kassay_akos Data 19 noiembrie 2015 13:35:56
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
using namespace std;
const int nmax = 10000000;

int n,v[nmax],g[nmax];


void read();
void redixSort();

int main()
{
    freopen("radixsort.out","w",stdout);
    read();
    redixSort();
    for(int i = 0; i < n; i+=10)
        printf("%d ",v[i]);
    fclose(stdout);
    return 0;
}

#define getByte(t) ((t >>( 8 * x))& 0xFF)
void countsort(int a[], int b[], int x) {
    int counting[257], indexing[257];
    memset(counting,0,4*(257));

    int w;
    for(int i = 0; i < n; i++){
        w = getByte(a[i]);
        counting[w]++;
    }
    w = 0;
    for(int i = 0; i < 256; i++) w +=counting[i];
    indexing[0]=0;
    for(int i =1 ; i < 256; i++)
        indexing[i] = indexing[i-1] + counting[i-1] ;

    for(int i = 0; i<n ; i++)
        b[indexing[getByte(a[i])]++] = a[i];
}


void redixSort() {
    for ( int i = 0; i < 4 ; i++) {             // 32/4 = 8 bit at a time
        if (i%2 == 0)   countsort(v,g,i);
        else            countsort(g,v,i);
    }
}

void read(){
    int a,b,c;
    freopen("radixsort.in","r",stdin);
    scanf("%d %d %d %d", &n, &a, &b, &c);
    v[0] = b;
    for( int i = 1; i<n; i++)
        v[i] = (a*v[i-1] + b) % c;
    fclose(stdin);
}