Cod sursa(job #2906886)

Utilizator woodyinhoStoica Elias-Valeriu woodyinho Data 27 mai 2022 17:59:14
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>

std::ifstream f("radixsort.in");
std::ofstream g("radixsort.out");

int n, v[10000005], A, B, C;

int get_maxim(int array[], int n) {
    int maxx = array[0];
    for (int i = 1; i < n; i++)
        if (array[i] > maxx)
            maxx = array[i];
    return maxx;
}

void countingSort(int arr[], int sizee, int place) {
    const int maxx = 10;
    int output[sizee];
    int countt[maxx];

    for (int i = 0; i < maxx; ++i)
        countt[i] = 0;

    for (int i = 0; i < sizee; i++)
        countt[(arr[i] / place) % 10]++;

    for (int i = 1; i < maxx; i++)
        countt[i] += countt[i - 1];

    for (int i = sizee - 1; i >= 0; i--) {
        output[countt[(arr[i] / place) % 10] - 1] = arr[i];
        countt[(arr[i] / place) % 10]--;
    }

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

void radixsort(int arr[], int sizee) {
    int maxx = get_maxim(arr, sizee);

    for (int place = 1; maxx / place > 0; place *= 10)
        countingSort(arr, sizee, place);
}

int main()
{
    f >> n;
    f >> A >> B >> C;
    v[0] = B;
    for(int i = 1; i < n; i++)
        v[i] = (A * v[i-1] + B) % C;

    radixsort(v, n);
    for(int i = 0; i < n; i += 10)
        g << v[i] << " ";

    f.close();
    g.close();
    return 0;
}