Cod sursa(job #547624)

Utilizator test9cosmin Macovei test9 Data 6 martie 2011 15:49:20
Problema Sortare prin comparare Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
//A program to implement Heap Sort

#include<cstdio>
using namespace std;
void Hup(int*,int);
void Hdown(int*,int,int);
int a[500001],n,i,j;
int main(){
        
		freopen("algsort.in","rt",stdin);
		freopen("algsort.out","wt",stdout);
        scanf("%d",&n);
        for(i=1;i<=n;i++){
                scanf("%d",&a[i]);
                Hup(a,i);
        }
        j=n;
        for(i=1;i<=j;i++)        {
                int temp;
                temp=a[1];
                a[1]=a[n];
                a[n]=temp;
                n--;
                Hdown(a,1,n);
        }
        n=j;
        //printf("sortare  ");
        for(i=1;i<=n;i++)
                printf("%d ",a[i]);
		printf("\n");
		return 0;
}
void Hup(int *a,int i){
        int v=a[i];
        while((i>1)&&(a[i/2]<v)){
                a[i]=a[i/2];
                i=i/2;
        }
        a[i]=v;
}
void Hdown(int *a,int i,int n){
        int v=a[i];
        int j=i*2;
        while(j<=n)        {
                if((j<n)&&(a[j]<a[j+1]))j++;
                if(a[j]<a[j/2]) break;
                a[j/2]=a[j];
                j=j*2;
        }
        a[j/2]=v;
}