Cod sursa(job #3040000)

Utilizator Beverita2345Bretan Alexandru Beverita2345 Data 29 martie 2023 10:49:55
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("radixsort.in");
ofstream out("radixsort.out");

const int NMAX = 1e7;

int v[NMAX + 5];

void NumberSort(int a[],int radix,int exp,int minim){
    int bucketidx;
    int bucket[radix];
    int output[a[0]];

    memset(bucket,0,sizeof(bucket));

    for(int i(1);i<=a[0];i++){
        bucketidx=(int)((a[i]-minim)/exp)%radix;
        bucket[bucketidx]++;
    }

    for(int i(1);i<radix;i++)bucket[i]+=bucket[i-1];

    for(int i(a[0]);i>0;i--){
        bucketidx=(int)((a[i]-minim)/exp)%radix;
        output[--bucket[bucketidx]]=a[i];
    }

    for(int i(1);i<a[0];i++)a[i]=output[i];

}

void Sort(int a[],int n,int radix){
    if(n==0)return;

    int minim=a[1],maxim=a[1];

    for(int i=1;i<=n;i++)minim=min(minim,a[i]),maxim=max(maxim,a[i]);

    int exp=1;

    while((maxim-minim)/exp>=1){
        NumberSort(a,radix,exp,minim);
        exp*=radix;
    }
}

int main()
{
    int n,a,b,c;

    in>>n>>a>>b>>c;

    int x=b;

    for(int i(1);i<=n;i++){
        v[++v[0]]=x;
        x=(a*x+b)%c;
    }

    Sort(v,n,10);

    for(int i(1);i<=n;i+=10){
        out<<v[i]<<' ';
    }

    return 0;
}