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

#include "timer.h"

int NBR = 10000000;
int MAX = INT_MAX;
int *TAB, *ALEA;


void randomize(int *T, int n) {
  int i;
  for(i=0;i<n;i++){
    T[i] = random();
  }
}

/* Arrange the N elements of ARRAY in random order.
   Only effective if N is much smaller than RAND_MAX;
   if this may not be the case, use a better random
   number generator. */
void shuffle(int *array, size_t n)
{
    if (n > 1) 
    {
        size_t i;
        for (i = 0; i < n - 1; i++) 
        {
          size_t j = i + random() / (RAND_MAX / (n - i) + 1);
          int t = array[j];
          array[j] = array[i];
          array[i] = t;
        }
    }
}

void init(int nbr) {
  ALEA = (int*)calloc(nbr,sizeof(int));
  randomize(ALEA,nbr);
}

int test(int nbr, int nb_tests){
  int i,k;
  int min, max;
  int total_min=0,total_max=0;

  init(nbr);
  
  init_timer;

  double time1=0,time2=0;

  for (k = 0; k < nb_tests; ++k)
  {
    
    min = MAX + 1; max = -1;

    first_step_timer;
    for(i=0;i<nbr;i+=2){
      int a1=ALEA[i], a2=ALEA[i+1];
      if (a1 < a2) {
        if (a1 < min) min = a1;
        if (a2 > max) max = a2;
      }
      else {
        if (a2 < min) min = a2;
        if (a1 > max) max = a1;
      }
    }
    second_step_timer;
    time1+=tim1;

    total_min += min; total_max += max;


    min = MAX + 1; max = -1;

    first_step_timer;
    for(i=0;i<nbr;i++){
      int a1=ALEA[i];
      if (a1 < min) 
        min = a1;
      if (a1 > max) 
        max = a1;
    }

    second_step_timer;

    time2+=tim1;


    total_min += min; total_max += max;
  
    shuffle(ALEA,nbr);
  }

  printf("%d\t%lf\t%lf\n", nbr,time1/nb_tests,time2/nb_tests);
  return total_max - total_min;
}

int main() {
  int i=0,j;
  srandom(time(NULL));

  int nb = 1000;

  for(j=0; j<18; j++){
    i+=test(nb,10);
    nb*=2;
  }

  printf("%d\n",i);
  return 0;
}