Cod sursa(job #2554960)

Utilizator KPP17Popescu Paul KPP17 Data 23 februarie 2020 15:45:17
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
/**
radix sort: O( baza * n * log(baza, maximum) )
(maximum = c)

ne avantajeaza mai mult sa scadem din baza direct
decat sa marim baza ca sa scadem logaritmul
pentru ca logaritmul creste logaritmic
si baza creste linear
linear > logaritmic

hai sa setam baza la 2
ar trebui sa obtinem
O( 2*n*lb(maximum) )
adica O(64*n)

ceea ce ar trebui sa fie accentuat
de comfortul calculului cu 2 pe care il au procesoarele



acesta este un program general pentru baza putere de 2
**/

#define fisier "radixsort"

#ifdef consola

    #include <iostream>
    #define in std::cin
    #define out std::cout

#else

    #include <fstream>

    #ifndef fisier
        #define fisier "HYPER"
    #endif

    std::ifstream in(fisier ".in");
    std::ofstream out(fisier ".out");

#endif



const int
MAX_N = 10000000, // 10 000 000
BAZA_BINARA = 8,
BAZA = 1 << BAZA_BINARA;



inline int getCif(int x, int z) {

    return (x >> z) & (BAZA - 1);

}



void cifSort(int* v, int n, int z) {

    static int aux[MAX_N], frecv[BAZA];



    for (int i = 0; i < n; i++) {

        frecv[getCif(v[i], z)] ++;

    }

    for (int cif = 1; cif < BAZA; cif++) {

        frecv[cif] += frecv[cif - 1];

    }



    for (int i = n - 1; i >= 0; i--) {

        aux[-- frecv[getCif(v[i], z)]] = v[i];

    }



    for (int i = 0; i < n; i++) {

        v[i] = aux[i];

    }

    for (int cif = 0; cif < BAZA; cif++) {

        frecv[cif] = 0;

    }

}



void radixSort(int* v, int n) {

    for (int z = 0; z < 32; z += BAZA_BINARA) {

        cifSort(v, n, z);

    }

}



int v[MAX_N];

int main() {

    int n, a, b, c;

    in >> n >> a >> b >> c;

    *v = 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) {

        out << v[i] << ' ';

    }

}






















//