#define  MaxN        20000

#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#include "math.h"
#include "time.h"


struct par
{
  int i1;
  int i2;
};

struct tripla
{
  int i0;
  int i1;
  int i2;
};

long int I_SEED = 1234567;

/* Prototypes */

float clockT ();
float randmM ();

int fib0( int );
struct par fib1 (int );
int fib2( int );

int hpfV(int );
int hsV(int );
int DhpfV(int , int );
int DhsV(int , int );
int inssV(int );
int mergeV(int , int, int );
int msV( int , int );

struct tripla soma_fib (int );
struct par minmax (int , int );

/*   --->  I/O variables  */

char  file_code[4];

FILE  *p_out;


int   Contador;
int   F_anterior;

int   V[MaxN + 1];
int   Temp[MaxN + 1];

/****************************************************************/
/*								*/
/*								*/
/****************************************************************/

main()

{
  struct par mima;
  struct par fibon;
  struct tripla som_fib;
  int i,k, ddd;
  int num;
  int num_fib;

  printf("Clock: %f \n", clockT() );


  do
    {
      printf("\n Tamanho do Conjunto:");
      scanf("%d", &num);
    }
  while ((num < 0) || (num > MaxN));


  printf("\n D da Heap:");
  scanf("%d", &ddd);

  /* Gera conjunto de inteiros */
     
  k = 0;
  for (i=1; i<=num; i++)
    {
      /*      V[i] = 2*i - 3; */
      V[i] = 1000 * randmM();
      printf("%4d ", V[i]);
      k++;
      if (k == 10)
	{
	  printf("\n");
	  k = 0;
	}
    }
  printf("\n");
  
  /*
  Contador = 0;
  mima = minmax(1, num);
  printf("\n\n Minimo e maximo do vetor: V[%d]=%d e V[%d]=%d \n",
	 mima.i1, V[mima.i1], mima.i2, V[mima.i2]);
  printf("\n Numero de comparacoes: %d \n", Contador);
  */
  
  /* k = DhpfV (num, ddd); */

  /* k = hsV(num);  */

  k = DhsV(num, ddd);

  /* k = inssV(num); */

  /* k = msV(1, num); */

  /* Imprime vetor de inteiros */
     
  k = 0;
  for (i=1; i<=num; i++)
    {
      printf("%4d ", V[i]);
      k++;
      if (k == 10)
	{
	  printf("\n");
	  k = 0;
	}
    }
  printf("\n");


  printf("Clock: %f \n", clockT() );

}

/****************************************************************/
/*								*/
/*								*/
/****************************************************************/


struct par minmax( inicio, fim )
int inicio, fim;
{
  struct par mm, mm1, mm2;
  int meio;

  /*  printf(" %d %d \n",inicio, fim); */
  
  if (fim - inicio <= 1)
    {
      Contador++;
      if( V[inicio] < V[fim] )
	{
	  mm.i1 = inicio;
	  mm.i2 = fim;
	}
      else
	{
	  mm.i1 = fim;
	  mm.i2 = inicio;
	}
    }
  else
    {
      meio = ((inicio + fim)/2);
      /*      printf("  %d \n",meio); */
      
      mm1 = minmax(inicio, meio);
      mm2 = minmax(meio+1, fim);

      Contador++;
      if ( V[mm1.i1] > V[mm2.i1] )
	{
	  mm.i1 = mm2.i1;
	}
      else
	{
	  mm.i1 = mm1.i1;
	}

      Contador++;
      if ( V[mm1.i2] < V[mm2.i2] )
	{
	  mm.i2 = mm2.i2;
	}
      else
	{
	  mm.i2 = mm1.i2;
	}
    }
  
  return( mm );
}      



/****************************************************************/
/*                                                              */
/*                                                              */
/****************************************************************/

int hsV( int n)
{
  int i, temp, stat;

  stat = hpfV(n);

  for (i=n; i>=2; i--)
    {
      temp = V[i];  V[i] = V[1];  V[1] = temp;

      stat = coloca_i (1, i-1);
    }
  return( 0 );
}


/****************************************************************/
/*                                                              */
/*                                                              */
/****************************************************************/

int DhsV( int n, int d)
{
  int i, temp, stat;

  stat = DhpfV(n, d);

  for (i=n; i>=2; i--)
    {
      temp = V[i];  V[i] = V[1];  V[1] = temp;

      stat = D_coloca_i (1, i-1, d);
    }
  return( 0 );
}


/****************************************************************/
/*                                                              */
/*                                                              */
/****************************************************************/


int hpfV(int n)
{
  int stat;
  int i;

  for (i= (int)(n/2); i>=1; i--)
    {
      stat = coloca_i (i,n);
    }
  return(0);
}


/****************************************************************/
/*                                                              */
/*                                                              */
/****************************************************************/


int DhpfV(int n, int d)
{
  int stat;
  int i, pai;

  pai = ((int)((n-2)/d)) + 1;
  for (i= pai; i>=1; i--)
    {
      stat = D_coloca_i (i,n,d);
    }
  return(0);
}


/****************************************************************/
/*                                                              */
/*                                                              */
/****************************************************************/



int coloca_i (int i,int n)
{
  int j, item, cont, k;

  j = 2*i;  item = V[i]; cont = 1;

  while ( (j <= n) && cont )
    {
      if ( (j < n) && (V[j] < V[j+1]) )
	{
	  j=j+1;
	}
      if (item >= V[j])
	{
	  cont = 0;
	}
      else
	{
	  k = (int)(j/2);
	  V[ k ] = V[j];
	  j = j*2;
	}
    }
  k = (int)(j/2);
  V[ k ] = item;
  return(0);
}


/****************************************************************/
/*                                                              */
/*                                                              */
/****************************************************************/



int D_coloca_i (int i,int n, int d)
{
  int j, f1, item, cont, k, max, fim, pai;

  cont = 1;
  item = V[i]; 
  f1 = d*(i-1) + 2;  
  pai = i;

  while ( (f1 <= n) && cont )
    {
      /* Acha indice do maior filho */

      j = f1;
      max = V[f1];

      if ((f1 + d - 1) > n)
	{
	  fim = n;
	}
      else
	{
	  fim = f1 + d - 1;
	}

      for (k = f1+1; k<=fim; k++)
	{
	  if (V[k] > max )
	       {
		 j=k; max=V[k];
	       }
	}

      if (item >= V[j])
	{
	  cont = 0;
	}
      else
	{
	  V[ pai ] = V[j];
	  pai = j;
	  f1 = d*(pai-1) + 2;  
	}
    }
  V[ pai ] = item;
  return(0);
}


/****************************************************************/
/*                                                              */
/*                                                              */
/****************************************************************/

int inssV(int n)
{
  int i, j, temp;

  for (j=2; j<=n; j++)
    {
      temp = V[j];

      i = j - 1;

      while ( (i>0) && (V[i] > temp) )
	{
	  V[i+1] = V[i];
	  i = i - 1;
	}
      V[i+1] = temp;
    }
  return(0);
}

/****************************************************************/
/*                                                              */
/*                                                              */
/****************************************************************/


float randmM ( )
{
  long int i,j;

  I_SEED = 16807 * I_SEED;

  if (I_SEED < 0)
    {
      I_SEED += 2147483647;
    }

  i = I_SEED / 32767;
  j = I_SEED - i * 32767;

  return( ((float)j)/32767.);
}


/****************************************************************/
/*                                                              */
/*                                                              */
/****************************************************************/

int msV( int i, int f )
{
  int m, stat;

  if ( i < f )
    {
      m = (int)((i + f)/2.);

      stat = msV(i , m);
      stat = msV(m+1, f);
      stat = mergeV(i, m, f);
    }
  return(0);
}


/****************************************************************/
/*                                                              */
/*                                                              */
/****************************************************************/

int mergeV(int l, int m, int f)
{
  int i, j, k, h;

  h = l; i=l; j=m+1;

  while ( (h<=m) && (j <= f) )
    {
      if ( V[h] <= V[j] )
	{
	  Temp[i] = V[h];
	  h++;
	}
      else
	{
	  Temp[i] = V[j];
	  j++;	  
	}
      i++;
    }

  if ( h > m )
    {
      /* A parte inferior foi toda percorrida */

      for (k=j; k<=f; k++) 
	{
	  Temp[i]=V[k];
	  i++;
	}

    }
  else
    {
      /* A parte superior foi toda percorrida */

      for (k=h; k<=m; k++) 
	{
	  Temp[i]=V[k];
	  i++;
	}

    }

  for (k=l; k<=f; k++)
    {
      V[k] = Temp[k];
    }

  return(0);
}

/****************************************************************/
/*                                                              */
/*                                                              */
/****************************************************************/

float clockT ( )
{
    unsigned long int ti;

    ti = clock();
    return( ((float)ti)/1000000. );

}