Cod sursa(job #1466924)

Utilizator mihaiadelinamihai adelina mihaiadelina Data 31 iulie 2015 23:17:46
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
using namespace std;

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

int tmp[10000001], a[10000001], bucket[10][10000001];

void radixSort (int n) {
    int i, nr, buckCount[10], divisor = 1, r, k, j, l;

    //gasim numarul maxim in lista data:
    int maxNumber = a[0];
    for (i = 1; i <= n; i++) {
        if (a[i] > maxNumber) {
            maxNumber = a[i];
        }
    }

    //aflam cate cifre are cel mai mare numar gasit:
    nr = 0;
    while (maxNumber != 0) {
        nr++;
        maxNumber /= 10;
    }

    for (i = 0; i < n; i++) {
        tmp[i] = a[i];
    }

    for (j = 0; j < nr; j++) {
        for (k = 0; k < 10; k++) {
            buckCount[k] = 0;
        }
        //Initialize bucket count;
        for (i = 0; i < n; i++) {
            r = (tmp[i] / divisor) % 10;
            bucket[r][buckCount[r]++] = tmp[i];
        }

        // colectam elementele din bucket
        for (k = 0, i = 0; k < 10; k++) {
            for (l = 0; l < buckCount[k]; l++)
                tmp[i++] = bucket[k][l];
        }
        divisor *= 10;
    }

    for (i = 0; i < n; i++) {
        a[i] = tmp[i];
    }
}

int main() {
    int N, A, B, C, i;
    fin >> N >> A >> B >> C;

    a[0] = B;
    for (i = 1; i < N; i++) {
        a[i] = (A * a[i - 1] + B) % C;
    }

    radixSort(N);

    for (i = 0; i < N; i += 10) {
        fout << a[i] << " ";
    }

    return 0;
}