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


void bestCase(int *v, unsigned int n)
{
    unsigned int i;
    for(i=0;i<n;i++)
    	v[i] =i;
}

void badCase(int *v, unsigned int n)
{
    int i,j;

    for(j=0,i = n;j  < n ;j++,i--)
         v[j] = i;
}

void mediumCase(int *v,unsigned int n)
{
    int i;
    randomize();
    for(i=0;i < n; i++)
        v[i] = rand() % n;
}


long heapsort(int arr[], unsigned int N)
 {
        long trocas =0;
     unsigned int n = N, i = n/2, parent, child;
     int t;

     for (;;) {
         if (i > 0) {
             i--;
             t = arr[i];
         } else {
             n--;
             if (n == 0) return trocas;
             t = arr[n];
             arr[n] = arr[0];
         }

         parent = i;
         child = i*2 + 1;

         while (child < n) {
             if (child + 1 < n  &&  arr[child + 1] > arr[child]) {
                 child++;
             }
             if (arr[child] > t) {
                 arr[parent] = arr[child];
                 parent = child;
                 child = parent*2 + 1;
                 trocas = trocas +1;
                 } else {
                 break;
             }
         }
         arr[parent] = t;
     }

 }


 main()
 {

  int *v;
  int debug;
  char f;
  unsigned int tam,i=0;
  long  trocas;
   long ratio;
   clock_t time1;
   clock_t time2;


  trocas = 0;

  if(!v)
  {
        puts("erro Alocacao vetor");
        exit(1);
  }

 do
 {


 printf("\nSize of Array: ");
 scanf("%i",&tam);


  v = (int *) calloc(tam,sizeof(int));

 bestCase(v,tam);
 #ifdef DEBUG

 puts("\nANTES");
 for(i=0;i<50;i++)
 		printf("\t%d",v[i]);
  puts("");
 #endif

 time1 = clock();
 trocas = heapsort(v,tam);
 time2 = clock();



 #ifdef DEBUG

 puts("\nDEPOIS");
 for(i=0;i<50;i++)
 		printf("\t%d",v[i]);
  puts("");
 #endif
  printf("\nBestCase %f seconds to execute.", (time2 - time1)/CLK_TCK);
 printf("\nSwaps %ld",trocas);

 trocas = 0;
 badCase(v,tam);
 #ifdef DEBUG

 puts("\nANTES");
 for(i=0;i<50;i++)
 		printf("\t%d",v[i]);
  puts("");
 #endif


 time1 = clock();
 trocas = heapsort(v,tam);
 time2 = clock();

 #ifdef DEBUG

 puts("\nDEPOIS");
 for(i=0;i<50;i++)
 		printf("\t%d",v[i]);
  puts("");
 #endif
  printf("\nBadCase %f seconds to execute.",(time2 - time1)/CLK_TCK);
 printf("\nSwaps %ld",trocas);



 trocas = 0;
 mediumCase(v,tam);
 #ifdef DEBUG
 puts("\nANTES");
 for(i=0;i<50;i++)
 		printf("\t%d",v[i]);
  puts("");
 #endif
 time1 = clock();
 trocas = heapsort(v,tam);
 time2 = clock();

 #ifdef DEBUG

 puts("\nDEPOIS");
 for(i=0;i<50;i++)
 		printf("\t%d",v[i]);
  puts("");
 #endif puts("\nf para sair");
 printf("\nMediumCase %f seconds to execute.",(time2 - time1)/CLK_TCK );
 printf("\nSwaps %ld",trocas);

 puts("\n\nf para sair");
 f = getch();
 }while(f != 'f');

 }