Cod sursa(job #563428)

Utilizator Robert29FMI Tilica Robert Robert29 Data 25 martie 2011 09:02:22
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<stdio.h>
FILE*f=fopen("algsort.in","r");
FILE*g=fopen("algsort.out","w");
int ok,i,son,n,v[500002];
inline int max(int a,int b){
	if(a<b)
		return b;
	else return a;
}
void insert(int x){
	int k=v[x];
	while(x>1&&v[x/2]<k){
		v[x]=v[x/2];
		x=x/2;
	}
	v[x]=k;
}
void down(int x){
	int k=v[1];
	int j=1;
	ok=1;
	while(ok&&(2*j)<=x){
		son=0;
		if(v[2*j]>k)
			son=2*j;
		if((2*j+1)<x)
			if(v[2*j+1]>v[son]&&v[2*j+1]>k)
				son=2*j+1;
		if(son==0||son>=x)
			ok=0;
		else{
			v[j]=v[son];
			j=son;
		}
		
	}
	v[j]=k;
}
int main() {
	fscanf(f,"%d",&n);
	fscanf(f,"%d",&v[1]);
	for(i=2;i<=n;++i){
		fscanf(f,"%d",&v[i]);
		insert(i);
	}
	
	for(i=n;i>1;--i){
		int aux=v[i];
		v[i]=v[1];
		v[1]=aux;
		down(i);
	}
	
	for(i=1;i<=n;++i)
		fprintf(g,"%d ",v[i]);
	fclose(g);
	fclose(f);
	return 0;
}