Question

Se dau n cifre zecimale. Să se afişeze aceste cifre în ordine crescătoare. Fişierul de intrare cifreord.in conţine pe prima linie numărul n, iar pe următoarele linii n cifre zecimale separate prin spaţii. Fişierul de ieşire cifreord.out va conţine cele n cifre ordonate crescător, câte 20 pe o linie, valorile de pe fiecare linie fiind separate prin spaţii. Ultima linie a fişierului poate conţine mai puţin de 20 de valori.

Answer 1

#include <iostream>
using namespace std;
ofstream fout("cifreord.out");
ifstream fin("cifreord.in");
const int NMAX = 500005;

int n, v[NMAX];

inline int father(int nod)     { return nod / 2; }
inline int left_son(int nod)   { return nod * 2; }
inline int right_son(int nod)  { return nod * 2 + 1; }

void go_down(int nod, int lg)
{
    int son = 1;

    while(son) {
        son = 0;
        if(left_son(nod) <= lg) {
            son = left_son(nod);
            if(right_son(nod) <= lg && v[right_son(nod)] > v[son])
                son = right_son(nod);
            if(v[son] < v[nod])
                son = 0;
        }

        if(son) {
            swap(v[son], v[nod]);
            nod = son;
        }
    }
}

void build_heap() { for(int i=n/2; i; i--) go_down(i, n); }

void heapsort()
{
    build_heap();
    for(int i=n; i>=2; i--) {
        swap(v[i], v[1]);
        go_down(1, i-1);
    }
}

int main()
{
    fin >> n;
    for(int i=1; i<=n; i++) fin >> v[i];
    heapsort();
    for(int i=1; i<=n; i++) {
        fout << v[i] << ' ';
        if(!(i % 20)) fout << '\n';
    }
    return 0;
}