Cod sursa(job #567238)

Utilizator mihai995mihai995 mihai995 Data 29 martie 2011 21:20:52
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 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>>1)])
	{
		sch(v[x],v[(x>>1)]);
		up((x>>1));
	}
}

inline void down(int x)
{
	int m=x;
	if ((x<<1)<=v[0] && v[m]>v[(x<<1)])
		m=(x<<1);
	if ((x<<1)<v[0] && v[m]>v[(x<<1)+1])
		m=(x<<1)+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]);
	}
	v[0]--;
	while (n--)
	{
		out<<v[1]<<" ";
		v[1]=v[v[0]--];
		down(1);
	}
	out<<"\n";
	return 0;
}