Cod sursa(job #567233)

Utilizator mihai995mihai995 mihai995 Data 29 martie 2011 21:15:51
Problema Sortare prin comparare Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>
using namespace std;

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

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

inline void sch(int &a,int &b)
{
	int c=a;a=b;b=c;
}

inline void up(int x)
{
	if (x>1 && v[x]<v[x/2])
	{
		sch(v[x],v[x/2]);
		up(x/2);
	}
}

inline void down(int x)
{
	int m=x;
	if (2*x<=v[0] && v[m]>v[2*x])
		m=2*x;
	if (2*x<v[0] && v[m]>v[2*x+1])
		m=2*x+1;
	if (m!=x)
	{
		sch(v[m],v[x]);
		down(m);
	}
}

int main()
{
	in>>n;
	for (v[0]=1;v[0]<=n;v[0]++)
	{
		in>>v[v[0]];
		up(v[0]);
	}
	while (n--)
	{
		out<<v[1]<<" ";
		v[1]=v[v[0]--];
		down(1);
	}
	out<<"\n";
	return 0;
}