infoarena

#include <stdlib.h>
#include <memory.h>

void _RTL_FUNC quicksort(const void *base, int lo, int hi, size_t width,
						int (*compare)(const void *elem1, const void *elem2), char *buf)
{

    if (hi > lo) {
        int i=lo, j=hi;
	    char * celem = buf + width;
        memcpy(celem,((char *)base) + width * ((lo + hi) / 2),width) ;

        while (i <= j)
        {
            while (i <= hi && (*compare)((char *)base + i * width, celem) <0) i++; 
            while (j >= lo && (*compare)((char *)base + j * width, celem) >0) j--; 
            if (i<=j)
            {
			    memcpy(buf, (char *)base + i * width, width) ;
			    memcpy((char *)base + i * width, (char *)base + j * width, width) ;
			    memcpy((char *)base + j * width, buf, width) ;
                i++; j--;
            }
        }
        if (lo<j) quicksort(base, lo, j,width,compare,buf);
        if (i<hi) quicksort(base, i, hi,width,compare,buf);
    } 

}
void _RTL_FUNC qsort(const void *base, size_t num, size_t width,
						int (*compare)(const void *elem1, const void *elem2))
{
    char data[512];
	char *buf ;

    if (width <= sizeof(data)/2)
        buf = data;
    else {
        buf = malloc(width) ;
	    if (!buf)
		    return ;
    }
    
	quicksort(base,0,num-1,width, compare,buf) ;

    if (buf != data)
    	free(buf) ;
}

#include <stdio.h>
#include <conio.h>

void heapsort(int[],int);

void main(){
	clrscr();
	int i;
	int a[]={1,56,23,52,47,79,12,97};
	for(i=sizeof(a)/sizeof(*a);i>1;i--)
	  heapsort(a,i-1);
	for(i=0;i<sizeof(a)/sizeof(*a);i++)
	  printf("%4d",a[i]);
	getch();
}

void heapsort(int a[],int limita_a){
	int i,o;
	int fiu_stanga,fiu_dreapta,fiu_mijloc,radacina,temp;
	radacina=(limita_a-1)/2;
	for(o=radacina;o>=0;o--){
	  for(i=radacina;i>=0;i--){
	    fiu_stanga=2*i+1;
	    fiu_dreapta=2*i+2;
	    if((fiu_stanga<=limita_a)&&(fiu_dreapta<=limita_a)){
	      if(a[fiu_dreapta]>a[fiu_stanga])
		fiu_mijloc=fiu_dreapta;
	      else
                fiu_mijloc=fiu_stanga;
	    }else{
	      if(fiu_dreapta>limita_a)
		fiu_mijloc=fiu_stanga;
	      else
                fiu_mijloc=fiu_dreapta;
	    }
	    if(a[i]<a[fiu_mijloc]){
	      temp=a[i];
	      a[i]=a[fiu_mijloc];
              a[fiu_mijloc]=temp;
            }
          }
	}
	temp=a[0];
	a[0]=a[limita_a];
	a[limita_a]=temp;
	return;
}

//Heapsort
#include <stdio.h>

int n, v[1000];

void swap(int x, int y)
{
   int aux;
   aux = v[x]; v[x] = v[y]; v[y] = aux;
}

void urc(int k)
{
   if (v[k] > v[(k-1)/2])
   {
      swap(k, (k-1)/2);
      urc((k-1)/2);
   }
}

void cobor(int k)
{
   int s, d, max;
   s = 2*k+1;
   d = 2*k+2;

   if (s < n && v[s] > v[k]) max = s;
   else max = k;

   if (d < n && v[d] > v[max]) max = d;

   if (max != k)
   {
      swap(k,max);
      cobor(max);
   }
}


int main()
{
   freopen("heapsort.in","r",stdin);
   freopen("heapsort.out","w",stdout);

   int i;

   scanf("%d",&n);
   for (i = 0; i < n; i++) scanf("%d", v+i);

   for (i = n - 1; i > 0; i--) urc(i);

   while (n > 1)
   {
      swap(0,n-1);
      n--;
      cobor(0);
   }

   for (i = 0; i < n; i++)  printf("%d ",v[i]);
   return 0;
}