Cod sursa(job #2124027)

Utilizator epermesterNagy Edward epermester Data 6 februarie 2018 20:13:42
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<fstream>
#include<vector>
using namespace std;
int n;

void heapify(vector<int>& x, int i) {
	int j = i * 2 + 1;
	if (i * 2 + 2 < n && x[i * 2 + 2] < x[i * 2 + 1])
		j = i * 2 + 2;
	if (x[i] > x[j]) {
		int aux = x[j];
		x[j] = x[i];
		x[i] = aux;
	}
	if(j<=n/2-1) heapify(x, j);
}

int main() {
	ifstream in("algsort.in");
	ofstream out("algsort.out");
	in >> n;
	vector<int> x;
	for (int i = 0;i < n;++i) {
		int temp;
		in >> temp;
		x.push_back(temp);
	}
	for (int i = n / 2 - 1;i >= 0;--i)
		heapify(x, i);
	while(n>0) {
		int aux = x[n-1];
		x[n-1] = x[0];
		x[0] = aux;
		out << x.back() << " ";
		x.pop_back();
		n--;
		if(n>1) heapify(x, 0);
	}
}