Cod sursa(job #567082)

Utilizator toniobFMI - Barbalau Antonio toniob Data 29 martie 2011 18:25:48
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
using namespace std;

ifstream in ("algsort.in");
ofstream out ("algsort.out");

const int N = 500003;
int n, v[N];

void reading () {
    in >> n;

    for (int i = 1; i <= n; ++i) {
        in >> v[i];
    }
}

inline int father (int poz) {
    return poz / 2;
}

inline int left_son (int poz) {
    return poz * 2;
}

inline int right_son (int poz) {
    return poz * 2 + 1;
}

void swap (int& x, int& y) {
    int aux = x;
    x = y;
    y = aux;
}

void heap_down (int heap[], int poz) {
    int l = left_son (poz), r = right_son (poz), best = poz;

    best = (l <= heap[0] && heap[l] > heap[best]) ? l : best;
    best = (r <= heap[0] && heap[r] > heap[best]) ? r : best;

    if (best != poz) {
        swap (heap[best], heap[poz]);
        heap_down (heap, best);
    }
}

void heap_up (int heap[], int poz) {
    if (poz != 1 && heap[poz] > heap[father(poz)]) {
        swap(heap[poz], heap[father(poz)]);
        heap_up (heap, father(poz));
    }
}

void build_heap (int heap[]) {
    for (int i = 1; i <= heap[0]; ++i) {
        heap_up (heap, i);
    }
}

void heap_sort (int heap[], int size) {
    heap[0] = size;

    build_heap (heap);

    for (int i = size; i >= 2; --i) {
        swap (heap[1], heap[i]);
        --heap[0];
        heap_down (heap, 1);
    }
}

void writeing () {
    for (int i = 1; i < n; ++i) {
        out << v[i] << ' ';
    }
    out << v[n] << '\n';
}

int main () {
    reading ();

    heap_sort (v, n);

    writeing ();

    return 0;
}