#include "func_array.h"

//-----[ Selection_sort ]--------------------------------------------------

void selection_sort  (int array[], int size) 
{
  int i, min, j , tmp;
  for(i = 0 ; i < size - 1 ; i++) 
    {
      min = i;

      // Find indice min
      for(j = i+1 ; j < size ; j++)
	if(array[j] < array[min])
	  min = j;

      if(min != i) // find or not.
	{
	  tmp        = array[i];
	  array[i]   = array[min];
	  array[min] = tmp;
	}
    }
}

//-----[ insertion_sort ]--------------------------------------------------
void insertion_sort (int array[], int size) 
{
  /* Spécifications externes : Tri du tableau t par insertion séquentielle */
  int i,pos,j,tmp;

  for (i = 1 ; i < size ; i++) 
    {
      /* Calcul de la position d'insertion pos : */
      /* détermine le plus petit indice pos       / 0 <= pos <= i */
      /* qui vérifie array[pos] >= array[i] */
      pos = 0;
      
      while(array[pos] < array[i]) 
	pos++;
      
      tmp = array[i]; /* Sauvegarde de t[i] */
 
      for(j = i-1 ; j >= pos  ; j--)
	array[j+1] = array[j]; /* translation de t[pos..i-1] vers t[pos+1..i] */
      
      array[pos] = tmp; /* insertion de t[pos] */
    }
}

//-----[ QuickSort ]-------------------------------------------------------

// QuickSort
void quick_sort (int * array, int debut, int fin)
{
  int          gauche, droite;
  int          pivot;

  pivot = array[debut];

  for(gauche = debut, droite = fin; gauche < droite; )
    {
      
      for(;array[droite] > pivot; droite--);
            
      if(gauche != droite)
	{
	  array[gauche] = array[droite];
	  array[droite] = pivot;
	  gauche++;
	}
      
      for(; array[gauche] < pivot; gauche++);
            
      if(gauche != droite)
	{ 
	  array[droite] = array[gauche];
	  array[gauche] = pivot;
	  droite--;
	}
    }
  
  if(debut < gauche-1) quick_sort(array, debut   , gauche-1);
  if(fin   > gauche+1) quick_sort(array, gauche+1, fin     );
}

//-----[ BubbleSort ]------------------------------------------------------

void bubble_sort (int array[], unsigned int size) 
{
  int i   = 0; /* Indice de répétition du tri */
  int j   = 0; /* Variable de boucle */
  int tmp = 0; /* Variable de stockage temporaire */
  
  /* Booléen marquant l'arrêt du tri si le tableau est ordonné */
  int en_desordre = 1; 
  
  /* Boucle de répétition du tri et le test qui
     arrête le tri dès que le tableau est ordonné */
  for(i = 0 ; (i < size) && (en_desordre == 1); i++)
    {  
      /* Supposons le tableau ordonné */
      en_desordre = 0;
      
                /* Vérification des éléments des places j et j-1 */
      for(j = 1 ; j < size - i ; j++) 
	{
	  /* Si les 2 éléments sont mal triés */
	  if(array[j] < array[j-1])
	    {
	      /* Inversion des 2 éléments */
	      tmp        = array[j-1];
	      array[j-1] = array[j];
	      array[j]   = tmp;
	      
	      /* Le tableau n'est toujours pas trié */
	      en_desordre = 1;
	    }
	}
    }
}

//-----[ Algo ]------------------------------------------------------------

void array_tri_croissant (int * array, unsigned int size,int algo)
{
  switch (algo)
    {
    case 0 : bubble_sort    (array,size);     break;
    case 1 : selection_sort (array,size);     break;
    case 2 : insertion_sort (array,size);     break;
    case 3 : quick_sort     (array,0,size-1); break;
    default : break;
    }
}