Cod sursa(job #1040909)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 25 noiembrie 2013 09:17:35
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <cstdio>

using namespace std;
int h[500001],i,n;
void swap (int x ,int y)
{
    int aux;
    aux=h[x];
    h[x]=h[y];
    h[y]=aux;
}
void heapup( int k)
{
    int x;
    x=k/2;
    if(x>0){
    if(h[k]>h[x])
    {
        swap(k,x);
        heapup(x);
    }
    }
}
void buildh( int k)
{
    int i;
    for(i=1; i<=n; i++) heapup(i);
}
void heapdw( int r, int k)
{
    int st,dr,i;
    if(2*r<=k)
    {
        st=h[2*r];
        if(r*2+1<=k) dr=h[2*r+1];
        else dr=st-1;
        if(st>dr) i=2*r;
        else i=2*r+1;
        if(h[r]<h[i])
        {
            swap(r,i);
            heapdw(i,k);
        }

    }
}
void heapsort(int k)
{
    while(k>0)
    {
        swap(1,k); k--;
        heapdw(1,k);
    }
}

int main()
{
    freopen("algsort.in","r",stdin);
    freopen("algsort.out","w",stdout);
    scanf("%d",&n);
    for(i=1; i<=n; i++)
    {
        scanf("%d",&h[i]);
    }
    buildh(n);
    heapsort(n);
    for(i=1;i<=n;i++)
    {
        printf("%d ",h[i]);
    }
    return 0;
}