Cod sursa(job #1707753)

Utilizator liviu23Liviu Andrei liviu23 Data 25 mai 2016 20:14:24
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stdio.h>
#define DIM 10000001
using namespace std;

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

void countSort(int bucket) {
    for(int i=0;i<n;i++)
        ord[(v[i]/bucket)%1000]++;
    for(int i=1;i<1000;i++)
        ord[i]+=ord[i-1];
    for(int i=n-1;i>=0;i--) {
        temp[ord[v[i]/bucket]%1000-1]=v[i];
        ord[(v[i]/bucket)%1000]--;
    }
    for(int i=0;i<n;i++)
        v[i]=temp[i];
}

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