Cod sursa(job #1708156)

Utilizator liviu23Liviu Andrei liviu23 Data 26 mai 2016 18:18:40
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <stdio.h>
#include <string.h>
#define DIM 10000005
#define RADIX_SIZE 8
using namespace std;

int n,a,b,c,v[DIM],temp[DIM];
int ord[300];

int getByte(int number, int bucket) {
    return ((number>>(bucket*RADIX_SIZE))&255);
}

void countSort(int bucket) {
    memset(ord,0,sizeof(ord));
    for(int i=0;i<n;i++)
        ord[getByte(v[i],bucket)]++;
    for(int i=1;i<=255;i++)
        ord[i]+=ord[i-1];
    for(int i=n-1;i>=0;i--) {
        int nr=getByte(v[i],bucket);
        temp[ord[nr]-1]=v[i];
        ord[nr]--;
    }
    for(int i=0;i<n;i++)
        v[i]=temp[i];
}

int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    scanf("%d%d%d%d",&n,&a,&b,&c);
    v[0]=b;
    for(int i=1;i<n;i++)
        v[i]=(1LL*a*v[i-1]+1LL*b)%c;
    for(int i=0;i<4;i++)
        countSort(i);
    for(int i=0;i<n;i+=10)
        printf("%d ",v[i]);
    return 0;
}