Cod sursa(job #2507568)

Utilizator gabriel.badeaGabriel Badea gabriel.badea Data 10 decembrie 2019 15:10:39
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include<iostream>
#include<stdio.h>
using namespace std;

#define NMAX 10000001

int N, A, B, C;
int arr[NMAX];

int getMax(int arr[NMAX], int n) {
    int maxValue = arr[0];
    for(int i = 1; i < n; ++i) {
        if(maxValue < arr[i]) {
            maxValue = arr[i];
        }
    }

    return maxValue;
}

int countSort(int arr[], int n, int digitOrder) {
    int output[n];
    int counter[10] = {0};

    for(int i = 0; i < n; ++i) {
        counter[(arr[i]/digitOrder)%10]++;
    }

    for(int i = 1; i < 10; ++i) {
        counter[i] += counter[i-1];
    }

    for(int i = n-1; i >= 0; i--) {
        output[counter[(arr[i]/digitOrder)%10]-1] = arr[i];
        counter[(arr[i]/digitOrder)%10]--;
    }

    for(int i = 0; i < n; ++i) {
        arr[i] = output[i];
    }
}

int radixsort(int arr[NMAX], int n) {
    int maxValue = getMax(arr, n);

    for(int exp = 1; maxValue / exp > 0; exp *= 10) {
        countSort(arr, n, exp);
    }

}

void print(int arr[], int n) {
    for(int i = 0; i < n; i += 10) {
        cout << arr[i] << " ";
    }
}

int main()
{
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);

    cin >> N >> A >> B >> C;
    arr[0] = B % C;
    for(int i = 1; i < N; ++i) {
        arr[i] = (1LL * A * arr[i-1] % C + B) % C;
    }

    radixsort(arr, N);
    print(arr, N);

    return 0;
}