Cod sursa(job #1708121)

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

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

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

void countSort(int bucket) {
    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%c;
    for(int i=1;i<n;i++)
        v[i]=(a*v[i-1]%c+b)%c;
    for(int i=0;i<4;i++) {
        countSort(i);
        memset(ord,0,sizeof(ord));
    }
    for(int i=0;i<n;i+=10)
        printf("%d ",v[i]);
    return 0;
}