////////////////////////////
/* Auteur : Stephen LABBE */
////////////////////////////


////////////////////////////
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>

#include "table.c"

 
void Echange (int * T, int p, int r)
{
int varlocal;
varlocal = T[p];
T[p] = T[r];
T[r] = varlocal;
}

int Partition(int * T, int p, int r)
{
int pivot, j, i;
//cpt++;
pivot = T[p];
i = p;
j = r;
	while(T[j]>pivot)
	{
		j=j-1;
	}
	while(i<j)
	{
		Echange(T,i,j);
		do j=j-1;
		while (T[j]>pivot);
		do i=i+1;
		while (T[i]<pivot);
	}
return(j);

}

/////////////////////Trirapide/////////////
void tri_rapide (int * T, int p, int r)
{
int q;
	if(p<r)
	{
		q=Partition(T,p,r);
		tri_rapide(T,p,q);
		tri_rapide(T,q+1,r);
	}
}


void  test ( void )
  {
  int n, *T;
  printf("\nVerification : ");
  for ( n = pas; n < nmax; n += pas ) {
    printf("\ntaille:%d", n);
    T = randtable( n );
    printable( T, n);
    tri_rapide(T, 0, n - 1); 
    printable( T, n);
    if( ! verification( T , n) )
           printf("\nErreur: Tableau non trié !");
    free( T );
  }  
  printf("\neot...\n");
  exit (0 ); 
  }


void testsortdata( void )
  {
  int n, *T;
  time_t deb, fin;
  double fc=0;
  printf("\nTemps de calcul table en ordre : ");
  pas = nmax / nblignes;
  for ( n = pas; n <= nmax; n += pas ) {
    T = sorttable( n );
    S = (int *) malloc(sizeof(int) * n); 
    deb = time( NULL );
    tri_rapide(T, 0, n - 1); 
    fin = time( NULL );
    fc += difftime( fin, deb )/n/n;
    printf("\nn= %d duree= %.2f", n, difftime( fin, deb ));
    free( S ); free( T );
  }
  printf("\nfacteur cache : %e\n", fc/nblignes);
  exit(0); 
  }

void testranddata( void )
  {
  int n, *T;
  time_t deb, fin;
  double fc=0;  
  printf("\nTemps de calcul table aleatoire : ");
  for ( n = pas; n <= nmax; n += pas ) {
    T = randtable( n );
    S = (int *) malloc(sizeof(int) * n); 
    deb = time( NULL );
    tri_rapide(T, 0, n - 1); 
    fin = time( NULL );
    fc = difftime( fin, deb )/n/log(n);
    printf("\nn= %d duree= %.2f", n, difftime( fin, deb ) ); 
    free( S ); free( T );
  }
  printf("\nfacteur cache : %e\n", fc/nblignes);
  exit(0); 
  }


int main (int argc ,char*argv[])
  {

  options( argc,argv );

  if ( check ) test ();
  if (   randopt ) testranddata(); 
  if ( ! randopt ) testsortdata();
 
  return 0; 
  }