Cod sursa(job #2635261)

Utilizator irimia_alexIrimia Alex irimia_alex Data 13 iulie 2020 20:08:25
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <stdio.h>
#define NMAX 10000001

using namespace std;

FILE* fin, * fout;
long long int n, v[NMAX + 1];
long long int tmp[NMAX + 1];

int getMaxNoOfDigits() {
    int max = v[1];
    for (int i = 2;i <= n;++i)
        if (v[i] > max) max = v[i];
    int nr = 0;
    do {
        ++nr;
        max /= 10;
    } while (max);

    return nr;
}

void sortByDigit(int p) {
    int count[10] = { 0 };
    for (int i = 1;i <= n;++i) {
        int digit = (v[i] / p) % 10;
        ++count[digit];
    }
    for (int i = 1;i <= 9;++i)
        count[i] += count[i - 1];
    for (int i = n;i > 0;--i) {
        int digit = (v[i] / p) % 10;
        tmp[count[digit]--] = v[i];
    }
    for (int i = 1;i <= n;++i)
        v[i] = tmp[i];
}

void radixSort() {
    int p = 1;
    int m = getMaxNoOfDigits();
    for (int i = 1;i <= m;++i) {
        sortByDigit(p);
        p *= 10;
    }
}

int main()
{
    fin = fopen("radixsort.in", "r");
    fout = fopen("radixsort.out", "w");

    int a, b, c;
    fscanf(fin, "%i %i %i %i", &n, &a, &b, &c);
    v[1] = b;
    for (int i = 2;i <= n;++i) {
        v[i] = (a * v[i - 1] + b) % c;
    }
    radixSort();
    for (int i = 1;i <= n;i+=10)
        fprintf(fout,"%i ", v[i]);

  
    return 0;
}