Cod sursa(job #2002935)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 21 iulie 2017 11:32:52
Problema Sortare prin comparare Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <cstdio>

FILE *in,*out;

using namespace std;

const int NMAX = 500000;

int v[1+NMAX],f[1+NMAX],sizeheap,heap[1+NMAX],sol[1+NMAX];

void swap(int a,int b)
{
    int tmp;
    tmp = heap[a];
    heap[a] = heap[b];
    heap[b] = tmp;
    tmp = f[heap[a]];
    f[heap[a]] = f[heap[b]];
    f[heap[b]] = tmp;
}

void urca(int p)
{
    if(p == 1)
        return;
    else
    {
        if(v[heap[p]] < v[heap[p/2]])
        {
            swap(p,p/2);
            urca(p/2);
        }
    }
}

void adauga(int x,int ind)
{
    sizeheap ++;
    heap[sizeheap] = ind;
    f[ind] = sizeheap;
    urca(sizeheap);
}

void coboara(int p)
{
    int dest = p;
    if(sizeheap >= p*2 && v[heap[p*2]] < v[heap[p]])
        dest = p*2;
    if(sizeheap >= p*2+1 && v[heap[dest]] > v[heap[p*2+1]])
        dest = p*2+1;
    if(dest != p)
    {
        swap(dest,p);
        coboara(dest);
    }
}

int main()
{
    in = fopen("algsort.in","r");
    out = fopen("algsort.out","w");
    int n;
    fscanf(in,"%d",&n);
    for(int i = 1;i <= n;i ++)
    {
        fscanf(in,"%d",&v[i]);
        adauga(v[i],i);
    }
    int ind = 0;
    while(sizeheap != 0)
    {
        swap(sizeheap,1);
        sol[++ind] = heap[sizeheap];
        sizeheap --;
        coboara(1);
    }
    for(int i = 1;i <= n;i ++)
    {
        fprintf(out,"%d ",v[sol[i]]);
    }
    return 0;
}