Cod sursa(job #1877180)

Utilizator SagunistuStrimbu Alexandru Sagunistu Data 13 februarie 2017 01:55:51
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int a[500005],n,auxn;

void read()
{
    fin>>n;
    for(int i=0;i<n;i++)
        fin>>a[i];
    auxn=n;
}

void heapify(int i)
{
    int largest,lc,rc;
    lc=2*i+1;
    rc=2*i+2;
    largest=i;
    if(lc<n&&a[lc]>a[largest])
        largest=lc;
    if(rc<n&&a[rc]>a[largest])
        largest=rc;
    if(largest!=i)
    {
        swap(a[largest],a[i]);
        heapify(largest);
    }
}


void write()
{
    for(int i=0;i<n;i++)
        fout<<a[i]<<" ";
    fout<<"\n";
}

void makeHeap()
{
    for(int i=n/2-1;i>=0;i--)
        heapify(i);
}

void heapSort()
{
    makeHeap();
    //write();
    while(n>1)
    {
        swap(a[0],a[n-1]);
        n--;
        heapify(0);
    }
    n=auxn;
}

int main()
{
    read();
    heapSort();
    write();
    return 0;
}