vineri, 14 septembrie 2018

Heapsort - operatii binare vector

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

# define MAX 100

int i,n,h[MAX];

void Scufunda(int n,int k)
{

int fiu=0;

//Se alege fiul cu valoarea mai mare
if((k<<1) < n)
 {
  fiu=k<<1;
  if(( ((k<<1)|1) < n) && (h[(k<<1)|1] > h[k<<1]))
   fiu=fiu|1;
  //Interschimbare numai daca este nevoie
  if(h[fiu] <= h[k]) fiu=0;
 }
else fiu=0;

while(fiu)
 {
  //Interschimbare
  int aux;
  aux=h[k];
  h[k]=h[fiu];
  h[fiu]=aux;
  k=fiu;
  //Se alege urmatorul fiu
  if((k<<1) < n)
  {
   fiu=k<<1;
   if(( ((k<<1)|1) < n) && (h[(k<<1)|1] > h[k<<1]))
    fiu=fiu|1;
  //Interschimbare numai daca este nevoie
  if(h[fiu] <= h[k]) fiu=0;
 }
 else fiu=0;
 }
}

void ConstruiesteHeap(int n)
{
int i;
for(i=(n>>1);i>0;i--)
 Scufunda(n,i);
}

void HeapSort(int n)
{
int i,aux;

ConstruiesteHeap(n);

for(i=n;i>=2;i--)
 {
 aux=h[1];
 h[1]=h[i];
 h[i]=aux;
 Scufunda(i,1);
 }

}

void main(void)
{
clrscr();

printf("Intr nr de elemente din sir: ");
 scanf("%d",&n);
printf("Intr elementele sirului:\n");
for(i=1;i<=n;i++)
 scanf("%d",&h[i]);

//
 HeapSort(n);
//

printf("\nAfisez sirul sortat:\n");
for(i=1;i<=n;i++)
 printf("%d ",h[i]);

getche();
}

Niciun comentariu:

Trimiteți un comentariu