Cod sursa(job #3346554)

Utilizator Sabin1133Padurariu Sabin Sabin1133 Data 14 martie 2026 10:55:22
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.26 kb
#include <iostream>

#define NMAX 10000000
#define RADIX 16

// linked list implementation
void linked_count_sort(int *v, int n, int radix, int base)
{
    int digit;
    int head[RADIX];
    int next[NMAX];
    int w[NMAX];

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

    for (int i = 0; i < n; ++i)
        next[i] = -1;

    for (int i = 0, j; i < n; ++i) {
        digit = (v[i] / base) % radix;

        if (head[digit] == -1) {
            head[digit] = i;
        } else {
            j = head[digit];

            while (next[j] != -1)
                j = next[j];

            next[j] = i;
        }
    }

    for (int k = 0, digit = 0; digit <= 9; ++digit)
        for (int j = head[digit]; j != -1; j = next[j])
            w[k++] = v[j];

    for (int i = 0; i < n; ++i)
        v[i] = w[i];
}

void naive_count_sort(int *v, int n, int radix, int base)
{
    int w[NMAX];

    for (int k = 0, digit = 0; digit <= 9; ++digit)
        for (int i = 0; i < n; ++i)
            if ((v[i] / base) % radix == digit)
                w[k++] = v[i];

    for (int i = 0; i < n; ++i)
        v[i] = w[i];
}

void count_sort(int *v, int n, int radix, int base)
{
    int count[RADIX];
    int index[RADIX];
    int w[NMAX];

    for (int digit = 0; digit < radix; ++digit)
        count[digit] = 0;

    for (int i = 0; i < n; ++i)
       ++count[(v[i] / base) % radix];

    index[0] = 0;

    for (int digit = 1; digit < radix; ++digit)
        index[digit] = index[digit - 1] + count[digit - 1];

    for (int i = 0; i < n; ++i)
        w[index[(v[i] / base) % radix]++] = v[i];

    for (int i = 0; i < n; ++i)
        v[i] = w[i];
}

void radix_sort(int *v, int n, int radix)
{
    int max;

    max = v[0];

    for (int i = 1; i < n; ++i)
        if (v[i] > max)
            max = v[i];

    for (int base = 1; base <= max && base != 0; base *= radix)
        count_sort(v, n, radix, base);
}

int main()
{
    int n, a, b, c;
    int v[NMAX];

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

    std::cin >> n >> a >> b >> c;

    v[0] = b;

    for (int i = 1; i < n; ++i)
        v[i] = (a * v[i - 1] + b) % c;

    radix_sort(v, n, RADIX);

    for (int i = 0; i < n; i += 10)
        std::cout << v[i] << ' ';

    std::cout << '\n';

    return 0;
}