/*--------------------------------------------------------*/
/* ------------ Les Tris de tableaux en C --------------- */
/* ------------ Laure Gonnord, oct 2004 ------------------*/
/*--------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "graphdsu.h"

#define NMAX 40
#define VALMIN 1
#define VALMAX 400

/*ne pas oublier les parentheses pour (j)*/
#define RECT(j) (RectanglePlein(13+10*(j),t[(j)],20+10*(j),0))

/*tire un entier au hasard entre inf et sup */
int hasard(int inf, int sup)
{
  int rando = rand();
  return (inf + (rando % (sup - inf +1)));
}

/*initialisation aleatoire du tableau*/
void initialise_tab(int t[NMAX])
{
  int i;
  for (i=0;i<=NMAX-1;i=i+1)
    {
      t[i]=hasard(VALMIN,VALMAX);
    }
}

/*visualisation du tableau sur le terminal*/
void visu_tab(int t[NMAX])
{
  int i;
  printf("[");
  for (i=0;i<NMAX-1;i=i+1)
    {
      printf(" %d ,",t[i]);
      if (i%10 == 9) 
	{printf("\n");}
    }

  printf(" %d ]\n\n",t[NMAX-1]);
}

/*echange de 2 cases (i et j)*/
void swap(int t[NMAX], int i, int j)
{
  int mem = t[i];
  t[i] = t[j];
  t[j] = mem;
}

/*tribulle, ma version*/
void tri_bulle(int t[NMAX])
{
  int j,k;
  for (j=NMAX;j>=1;j--)
    {
      for (k=0;k<=j-1;k++)
	{
	  if (t[k]>t[k+1]) {swap(t,k,k+1);}
	}
    }
}

/*procedure de tri croissant - version du cahier jaune*/
void tri_bulle2(int t[NMAX])
{
  int i,j;

  for (i=0;i<=NMAX-2;i++)
    {
      for (j=NMAX-1;j>=i+1;j--)
	{
	  if (t[j]<t[j-1]) {swap(t,j,j-1);}
	}
    }
}

/*tribulle graphique, version du cahier jaune*/
void tri_bulle_graphique(int t[NMAX])
{
  int i; int j;
  Initialiser(450,400);
  ChangeCouleur (3);

  /*affichage initial en bleu*/
  for (i=0;i<=NMAX-1;i++)
    {
      RECT(i);
    }

  /*tri et affichage*/
  for (i=0;i<=NMAX-2;i++)
    {
      for (j=NMAX-1;j>=i+1;j--)
	{
	  if (t[j]<t[j-1]) 
	    {
	      /*effacage des rectangles, ie dessin en blanc*/
	      ChangeCouleur (1);	      
	      RECT(j);RECT(j-1);

	      /*swap, temporisation*/
	      swap(t,j,j-1);
	      Attendre(50);

	      /*dessin des 2 rectangles a la place*/
	      ChangeCouleur (3);
	      RECT(j);RECT(j-1);
	    }
	}
    } 
  /*visualisation finale en jaune*/
  ChangeCouleur(5);
  for (i=0;i<=NMAX-1;i++)
    {
      RECT(i);
    }
  
  Cliquer();
  Clore();
}

/*tri insertion*/
void tri_insertion(int t[NMAX])
{
  int j,k;
  for (k=1;k<=NMAX-1;k++)
    {
    j = k;
    while ((t[j-1]>t[j]) && (j>1))
      {
	swap(t,j,j-1);
	j = j-1;
      }
    }
}

/*tri selection*/
void tri_selection(int t[NMAX])
{
  int  max_tmp,indice_max,k,i;
  for (k=NMAX-1;k>=1;k--)
    {
      max_tmp = t[0];
      indice_max = 0;
      for (i=1;i<=k;i++)
	{
	if (t[i]>max_tmp)
	  {
	    max_tmp = t[i];
	    indice_max = i;
	  };
	}
      swap(t,indice_max,k);
    }
}

int main(void)
{
  int tab[NMAX];

  /*initialisation du generateur de nb alea*/
  srand(time(NULL));  
  initialise_tab(tab);
  visu_tab(tab);
  //tri_selection(tab);
  /* visu_tab(tab); */
  
  tri_bulle_graphique(tab);
  visu_tab(tab); 

  return 0;
}

/* gcc  -lm -lX11 -lgraphdsu tribulle.c -o tribulle -L . -L /usr/X11R6/lib */