source: trunk/Softwares/Common/src/c/func_array.c @ 117

#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;
    }
}